My party would be:

Beatrix: Strong white magic + whoop-arse sword.
Tifa: Gotta have a Black Belt, and her limit rocks.
Lydia: For summoning and nuking.
Onion Kid 3: One of the four strongest swordmen in any FF. Besides, that party wouldn't need any more magic.