I really don't think Celes counts, as she's forced into your party, but the first time I played, the order of the others was determined by the Nintendo Power Strategy Guide I had got from Toys R Us. I think I have a scan of it somewhere, it has all this great Amano artwork.

Anyway, it was:

Sabin > Edgar > Setzer > Cyan > Gau > Relm > Strago > Terra > Locke > Mog > Umaro > Gogo.

You'll notice that I didn't recruit Shadow, and I'll give you three guesses why.