The optional dungeon I *believe* was Strago's side quest. IIRC it's actually a mountain, not (fully) a cave or dungeon, so Strago would obviously be in the party; it's those other guys that took some balls. I don't think the player realized Gogo's potential ("mimic" repeats the last action in battle, right? He never used it like that.)
The final dungeon/Kefka's tower was pretty tough, but he still was able to get through the game comfortably without taking much time building characters up. The side quests in the second world make you develop some of them.
Speaking of the second world: after you beat it, does the world stay shitty? It greens up in some cutscenes but still looks brown and dead in others. That would be a bummer if so!