I used Zidane, Dagger, Steiner and Vivi around level 60. Since I had Excalibur, Steiner did maximum damage with every attack and the fight was easy (until he cursed me, anyway )

PS. Does anyone else here recognize the music from when you fight Hades as being from FF8 when the SeeDs land at the beach during the Dollet mssion?