Locke: Get a Thief Glove, turn Steal into Capture. Use Odin to up his already above-average speed to a ridiculous number, and put a Zephyr Cape on him.

Celes: Equip the Atma Weapon on Terra instead, and then you can use Runic. Give her. . .oh, I don't know, Ragnarok or Illumina or something. Take advantage of her above-average magic power and up it with an Esper.

Strago: Beat Hidon. Use Relm with a FakeMustache and go to the Veldt and Control different enemies to learn more Lores with a significantly less risk factor. Then again, Grand Train is the only Lore worth using while you have it, anyway. Yeah, just beat Hidon.

Setzer: Fixed Dice + Offering + Black Belt + Paladin Shield + anything else = Mwa ha ha.

Mog: The only worthwhile dances after a while are Wind Song, Snowman Jazz and Water Rondo. Don't bother with the other ones.

Gogo: Let him be able to use Blitzes, Tools and Magic, then turn him loose. He may not be as powerful as a Sabin or a Terra, but a Bum Rush is still a Bum Rush.

Umaro: Give him a Gauntlet and a Rage Ring. Let everything else come as it may.

If you know what to use, you can make Shadow's Evade rate go upwards of 80%. I know because I've done it, and it's beautiful. Use Espers to up Relm's already-ridiculously-high magic power and let her learn Ultima, and you don't need to worry about anything else.