I would rather not see Mega Man in the game actually, he's really a boring character with little potential in my eyes =/ Zero would fit much better, but that would be weird, atleast without Mega Man.
Anywhoo,
Resident Evil- Leon, Could've been like Snake, with emphasis on different guns, grenades etc.
Final smash could be some real infected goodieness.
Or that Napoleon dwarf, damn that would rock.
Zelda - Link/Wolf would've been fun, even tho i hate TP from the bottom of my heart.
Skull kid from Majora's also would have been cool, but i cant really picture his.
moves etc.
Banjo Kaz. Yes, it would rock
Conker. Oh the taunts. =D
Tales Of.. - Like someone said, characters have lots of potential and the controls / abilities are already quite similar.
Final Fantasy, and no- not Cloud, someone else, someone like Cecil from 4, Terra from 6 or Squall from 8 comes to mind, all with lots of potential for abilities and final smashes.
And they could get rid of-
Sonic, Lucas, Olimar, ROB. Snake and Game & Watch for all i care. With emphasis on Sonic