My votes (Reasons in parenthesis)
Fire Emblem
Hector (very popular, and we need more non-sword FE characters)
Lyn/Lyndis (We need female FE representation, plus she's hot)
Roy (Obvious reasons, although he needs a ranged attack, since he could attack from a distance in Fuin no Tsurugi)
Micaiah (Again, female FE rep, and a magic user)
maybe Ike [Radiant Dawn/Vanguard] (Why not?)
Black Knight (He's awesome)
Ephraim (cool, plus with Hector, we would have the whole weapon triangle in Brawl)
Pokemon
Mewtwo (Obvious reasons)
Sonic
Shadow (popular, Chaos powers would allow him to have a non-Sonic-clone moveset)
Tails (would be interesting, been in pretty much every Sonic game since StH 2)
Knuckles (Again, been in almost every Sonic game since 3, and he's popular)
Silver (his psychic abilities would be interesting in Brawl, plus he's cool)
Amy (Piko Piko Hammer FTW!)
Star Fox
Krystal (obvious reasons)
A non-Fox-clone for Falco and Wolf
Metal Gear Solid
Naked Snake/Big Boss (would have a more grab-based playstyle than Snake, plus he's awesome)
The Boss (popular, one of the most important characters in MGS)
Raiden [Cyborg Ninja] (He's awesome, and he uses a sword instead of guns)
Mario
Bowser Jr./Shadow Mario (popular, and in most Mario games since his first appearance)
Dark Bowser (Awesome, plus could have a moveset that wouldn't be a Bowser-clone)
Other
Megaman (Obvious reasons)
Bomberman (Again, obvious reasons)
Geno (Need I say more?)
That's all I can think of now.