I've heard some pretty convincing logic that the last third party will be Sora, from Kingdom Hearts.
- he's iconic and popular enough
- square and nintendo have been having a secret relationship for years now. there are love-children. (ff3 for ds anyone?)
- he's VERY smashbrothersy. there's a huge list of moves that would make sense for him.
-also, KirbySora. Kirby with a keyblade is cooler than Kirby with sonic dash, sorry.
Besides that, when's the last time a Megaman game was very popular? I mean, sure, sonic's been out of the limelight for awhile, but he's still sonic. Megaman was never the center of attention like he was.
also, flying yoshi is cool, and so is Snake's lightgun game. The only one so far that I've been actively disappointed by was Zelda.