2 cents time:
Pac-Man
In my opinion, this should be the #1 3rd party choice, even more so than Sonic & Snake. Why? BECAUSE ITS FREAKING PAC-MAN!!!! You want "legend", well Pac goes beyond even that. He's the very symbol of 80s gaming & the only character in existence to exceed Mario in mainstream status, everyone knows of him. If you say he's a "waste" of a slot, then turn in your gamer card, you're out of the club. As far as moveset possibilities goes, there's the Pac-Man World games as sources of inspiration.
Simon Belmont
Smack me & I'll respond with something more painful. This guy should've gotten in before Snake. Come on, who cares about the NES Metal Gear? It's just a port of an MSX game & that series is far more prominent on Sony hardware. Plus, stealth action just plain sucks. Castlevania is far more prominent on Nintendo systems, from the NES to the DS & everywhere in between. Simon himself is clearly the true face of the franchise, being not only the original hero but also the most frequent with 7 different Castlevania games. In addition he has had playable roles in Konami crossovers like both Wai Wai Worlds & Dreammix as well as a somewhat unflattering cartoon role alongside Megaman. I can not fantom why so many people here don't think he's worthy, were you all born yesterday?
Geno
What's the argument here? He's listed as 1st party in Sakurai's poll, so it's all a null point. Oh wait, I have an argument......
Mallow
Geno this, Geno that. Geno Geno Geno. Why does he so much more attention than the other SMRPG characters? He has like 5 lines of dialouge, is pointless to have in your active party once you get Bowser (which is about 10 minutes later) & his only real purpose is to provide a bit of exposition that could've just as well been given by that old grandpa frog. Mallow on the other hand, has way more backstory, more personality, is the 1st character to join the party & has more intriguing moveset possibilities. I say screw Geno & put Mallow in his place.
Bomberman
Just for the record, Konami owns Hudson, so Bomberman would effectively be a Konami character. In any event, he's limited in moveset possibilities. It's just not in his character to do anything except drop a bomb. This was his only special move in Dreammix TV: World Fighters. Honestly, if Little Mac didn't amount to more than just AT, why could Bombie?
Megaman
After Pac-Man, he stands as the most likely inclusion. After all, if there's 1 thing Capcom's known for, it's milking franchises for every bit they're worth. His moveset potential is staggering if he has any boss weapons, but even without those his options are plentiful.
Sora
Sora is an up & comer in the world of video games, perhaps not quite a legend yet but well on his way. Sora would the Square character that I'd enjoy playing the most, both as a KH fan & because of moveset possibilities. Since CoM is his main Nintendo presence, he could stock attacks like he did with cards in that game & use them for slights. He's also quite fitting to the nature of SSB, his own series being a crossover. Unfortunately, it's hard to deny that he isn't the top dog of S-E, particularly since Disney owns him.
Master Chief
Microsoft owns him, not Bungie. Do not kid yourself in ever thinking otherwise. This ain't happening.
Banjo Kazooie
Same as the Chief, it's not happening. What I don't get however is why hasn't Rare made their own mascot fighter yet? They imitated Mario 64, Mario Kart 64 & even tried to take on Zelda with Dinosaur Planet/Star Fox Adventures. Yet the SSB clone is absent despite Rare's own plethora of characters. They could even get Halo characters in their hypothetical fighter now.