I'm ashamed to admit I never managed to play the Smash Bros games, but I intend to make up for that (DS version please?).
How about a Goomba? Or Pikmin? sonic? (given the availability of some Megadrive games for the virtual console bit). Toad? Metal Mario?
Or how about a bloody great comedy Mech, just to throw people off? 
I don't see much possibility of a DS version of SSB at all, considering the importance of analog control to the series. I cringe every time I hear someone suggest it would work. <_<
All I know is that it will be very interesting to see what other 3rd parties will make their way into this title (and other Ninty games as well). This trailer is just about all that exists of SSBB so far, meaning the slate is still very clean and will be able to incorperate any character desired, really.