I'll put them like this (Geno isn't counted since he is a third party character that starred with a 1st party character in his debut game):
1. Megaman (Classic, although I guess X, Legends and .EXE could be alternate costumes)
Megaman had more games come out for the NES then any other franchise. His spin-offs continue to appear on Nintendo handhelds and the occasional console. He'd fit Smash like a glove. WINNER!
2. Bomberman
As the only major 3rd party character to appear in a Nintendo game, Bomberman must be considered heavily.
3. Pac-Man
The third cog in the almighty wheel of Video Game mascots that transcend gaming. While he is very unlikely, I've always liked the idea of him being in, and his historic presence would be welcomed...
4. Ryu
Ryu would be cool, but is heavily unlikely, since he is already so identified with Street Fighter.