For this, you’ll first need the Excalipoor (irony - play FFV to learn why) to get Gilgamesh to come. You can get it at the Auction House in Jidoor; speak to the guy outside to make it available… and you’ll need 500,000 Gil.
Fight 50 Cactuars (25 with the Cat-Ear Hood and Relm) to get it. Also try to supply Hermes Shoes and Prayer Beads to your party. It might be a good aide. Fenrir, Phantom, and Zona Seeker are musts… … AND, FOR GOD’S SAKE, BRING LOCKE TO STEAL GENJI EQUIPMENT!
Anyway, head to the Dragon’s Neck Coliseum (north side of the northwest continent). Save outside and bring your fighting party (which really needs to have Locke; I can’t stress it enough), then bet the Excalipoor at the front desk. After the resulting battle, you’ll fight Gilgamesh. Far from his days of taking Excalipoors in chests, he now just mugs people for them. (Reference to FFV and FF: Dawn of Souls.)
Gilgamesh also has more impressive attacks than in previous FFs. He can use a basic attack, Blade Dance (basic attack with 50% more power), Aqua Breath, 1,000 Needles, Quasar , Revenge Blast, Throw, Jump , Aero, Dischord , and Stone. Haste, Protect, and Shell are used at one point.
Locke needs to do nothing but Steal the two Genji items first. Plain ‘n’ simple. Now, for a while, begin to boost your defenses: use Fenrir and Zona Seeker to start with; Phantom will lie in reserve for a second. Then just attack Gilgamesh for a bit with some physical attacks, preferably. Flare and Bahamut are still good for this, too.
After Gilgamesh stops playing around, he’ll cast Protect, Shell, and Haste and proceed to use a Jump, some quick Attacks, two turns of 9,999-damage Throws, and loop from there. To avoid this, once his protective spells are cast, use Phantom and simply Attack from there on out … or use more potent cough Ultima cough forms of violence; doesn’t matter, as you can’t be hit.
After the battle, you’ll receive the Gilgamesh Magicite , which teaches some of the best spells in the game. Take Valor for instance, which triples the damage of the character’s next attack. Cyan’s Tiger Bushido halves the target’s current HP; now the damage is 1.5x that! Excellent.