On my most recent playthroughs, I really changed up the order in which I picked up my characters. It looked something like this.

Celes->Sabin->Edgar->Setzer->Mog->Lock->Terra->Shadow->Relm->Strago->Cyan->Umaro->Gogo->Gau.

I never use Gau, hence the lack of love. I also always save Gogo and Umaro for later as I don't have to worry about teaching them anything.