Terra - Trumpet Thief (He has green hair)
Locke - Lynx (Duh)
Edgar - Loony BoB (Ladies' man)
Sabin - theundeadhero (Army!)
Shadow - Jojo (Shadow doesn't like Relm, plus her BF has many many swords.)
Cyan - sephirothishere (they both speak funny)
Gau - idk, maybe m4tt.
Celes - Old Manus (Works for the empire)
Setzer - Before I knew Raistlin's real age (16) I'd definitely put him here.
Mog - Baloki (I don't need a reason to associate Baloki with an animal.)
Strago - Alive Man
Relm - Psychotic
Gogo - Flying Mullet (aka Mr. Mimic)
Umaro - Obvious

Mayor of Zozo - Avarice