All of your Charcter ideas Are awsome, But from my past experience with SSBM and having to call nintendo to replace my Burned out Discs/Consoles because of SSBM Multiplayer. Here are a few of My Ideas on the game and how it should be Improved.
1. Single Player - Chuck it, Its Useless, repetive, and most of the time, way to friggin easy. The Space could be used for More Charcters/ Multiplayer levels/ Harder AI. Screw the trophy System, it was interesting at first but got tiresome.
2. Multiplayer - (Brace Yourself this is gonna be Long)
2a.*They need add Online Capabilities, Although Nintendo is Skeptical, they should do it, Simply because it would be awsome, and we could downlaod more Characters, their Only Paranoid because of the Load of Exploits it would open up fior hacking the Console.
*With Online Capabilities should Some some sort of Hard drive to Store the Various new Chars and maps That will be added over time, And an Ability to Hosts Games from your Console, So nintendo would have to spend cash on server support for us, and we wont have to wait to play. Im guessing it can placed kinda like the GBA or Broadband ADaptors. W/E nintendo can figure it out.
*Better Yet, Nintendo Should make some way of LANing Gamecubes together for like 4+ player Fights. I Mean in game SSBM Allowed what? 6, 8 Chars on the feild?
2b. For people who dont like Online Capabilties, Just Simple add a crapload of Charcters and Fun maps. MIN Characters could be 40-50? MAx could be 100, but then they would just be repeating fighting styles. Whihc would be lame. Kinda Like what tey did with ganondorf and Captain Falcon

They should have at least 30 Maps. Double of what SSBM Has currently.
2c. More Combos? And no B(UP) B(DN) Type Combos Something with a Challenge to it.
2d. The Engine is Just Fine, i love the fast pace of the game compared to the old one.
Extras - Im Not asking for much but How about Holiday varioations of the Charcters? Like during Christmas Mario Wears Green and red, Soemthign Like that, Too make it somwhat interesting. For Halloween they should make a few costumes for each year

. Up to Like 2008 or something.
Holiday Charcters? Like During Halloween Shadow Mario appears for the Day, baby Mario Comes out for new years

Stuff like that... People Might not like it but hey, EGM got us all excited.
Thats all i have. For Character ideas al of yours are awsome.