Travis Touchdown - Pretty straight forward: A = Sword, B = various of his other attacks/defenses, Grab = wrestling moves, smash ball activates one of the random powerups. the costumes selection alone would be so awesome.
that Morphing alien from Metroid Prime 3 - (basically let her work opposite of Kirby, her B move copies whoever is in front of her and teh closest, but copying replaces all of her moveset and weight and appearance EXCEPT for the regular B, which allows her to copy again)
King K. Rool would be a nice heavyweight to help balance things, no clue of his movesets though
Leave Donkey Kong in, but replace Diddy Kong with Dixie.
Leave Peach in, but give her some better moves, maybe based on that emotions thing that her DS game had. Her moves are way too weak or slow as they stand now.
Leave Mewtwo out, or improve his skills so he has better speed and power on the psychic moves, give him some honest levetation to balance out how dang light he is.
I want to agree with bomberman and megaman, but I'm not confident they have a diverse enough moveset, or in megaman's case, that he wouldn't come out as a samus clone, at least a little. At least pull him from Megaman X though. I liked the design and the stuff like powersliding and wall jumping so much better. maybe add in the dog to act as his Up B like how sonic gets the spring board?
I think I'd like to see the kid/toon link replaced with Midna w/Wolf Link. That would be an entirely fresh character for the game.
Jigglypuff seems unessesary, get rid of it or make it so that its rest attack actually recovers damage, I just cannot get how retarded it is that it can KO people with that move, and why is its sing attack so short range? seriously, i would be fine if you made jigglypuf even weaker as long as its moveset made freaking SENSE.
honestly though, i don't want to see more than 1 smash bros game per console. 1 for N64, 1 for Gamecube, 1 for Wii, that's great, the NuWii can have the next Smash Bros game as a launch title, that'll be perfect, but not while we're still on the Wii, please.