I used a party of Zidane, Steiner (shock/best limit break), Freya (for Dragon Crest; it did 9000+ damage, as I had spent much time killing Grand Dragons with Quina's Lv 5 Death ), and Garnet (she can cast Curaga; Eiko can't).
For tactics, I had Zidane attack and occasionally use Elixers to restore MP to Steiner, Steiner use Shock, or go into trance, in which he did 9999 damage with a regular attack, and Freya use Dragons Crest (and Rei's Wind, at the start). Garnet, of course healed and supported.
He is really not that hard; in one instance Grand Cross wiped out my entire party except for Steiner, who was raged (ie, I couldn't use Phoinex Downs), and he still died.
Unfortuneatly, the worst part of Grand Cross is the Death effect, and there is no way to prevent that, so defend yourself from what you think are the worst of the statuses (Blind, Confuse, Petrify, IMO) and fight onward, brave warrior.