My three choices would be:

Leo - Yes I went there.

Cid - Finally get something for saving his sorry ass. His special skill would be Scan which worked like Libra, and he would gain a relic that turned his ability into having the same effect as Edgar's Debilitator.

Biggs or Wedge - Only get one of them unless you ditch both Gogo and Umaro. They wouldn't get a special skill but rather have their Magitech Armor, but their skills would be restricted by which magic they had and they would even gain new ones that Terra doesn't get.

Gestahl would also be an interesting choice...