Some dark horses:
1. King Hippo (Punch Out)2. Andy (Advance Wars)
3. Jumpman (1981 Donkey Kong)
4. Space Pirate (Metroid Prime Design)
5. Mona (WarioWare Series)
King Hippo: two or more newcomers from the same series apparently isn't impossible, and Little Mac was one of the first newcomers to be revealed.
Andy: The Wars series is sadly under-represented, and Andy is more or less the face of it.
Jumpman: Swinging hammers, climbing ladders, leaping barrels, removing rivets, collecting purses... what a moveset.
Space Pirate: With Ridley a boss, Kraid a stage feature in Melee, and Mother Brain an assist trophy, who else?
Mona: Because all the WarioWare characters are extremely colorful and fleshed out, but Smash Brothers needs some more Smash Sisters. Besides, Mona has a scooter, pets, and amazing music.