When I fought him my party was Zidane, Quina, Freya, and Eiko. Zidane was easily the weakest character since he didn't have any attacks that did a sure 9,999 like everyone else. So I had to have him one hit away from Trance so he wouldn't drag my party down.

Quina comes in highly useful in this battle because she has so many great Blu Magics. If you use her, then Angel's Snack, Mighty Guard, and Frog Drop are lifesavers and make this battle much easier. Especially if Ozma uses Curse. You should definately have characters that do 9,999 too, like Freya and/or Steiner.

Anything else that I add will just be repeating what Chris posted in the quotes.