Well, let's bring something new in. (I say "new" very loosely)
Cloud Strife for Brawl.
May seem out there but if Square-Enix wants in it makes sense. Plus, he appeared breifly in Chain of Memories so he fits the criteria to get in. He'd be bloody fun to play as. You could have Cloud vs Sonic vs Mario vs Snake, how legendary is that? Plus throw in Chocobo, Moogles and Bahamut ATs; items like Mega Elixir (for Team Battles) or the Blood Sword; or how about a Stage? All Final Fantasy's have Airships so throw one of them in, flying through skies, seas, over land, through volacnoes, icey plains or even space.
Letting Cloud in opens up loads of doors for Final Fantascy related stuff, which could all be a hell of alot of fun.
Thoughts?