When I first played the game, I was very curious about the story so I spent little time level and as such I was incredibly underleveled... I got to the temple of the ancients and my cloud had about 750hp and was my strongest fighter. Poor Aerith didn't stand a chance as I hadn't used her at all had a measly 600hp (ish) and I got so owned by the Demon Gate... I nearly gave up. After a huge amount of grinding I finally beat him.

Ever since then I have made a point of being at least somewhat decently leveled when I go anywhere. As for Midgar Zolom I was warned prior to meeting him by the guy who introduced me into the series not to bother trying to fight him as "he has a move that does 4000 damage to you".