Play a lot of blitzball.
Use wings to discovery, I believe, on an armor, or defeat Omega Weapon, or fight Nemesis at the monster arena.
You can fight King Cactuar, but everything besides these two are much slower. It's your choice between fighting in the omega ruins, inside sin, or the monster arena bosses as random encounters.