Here's an idea. For third Party characters they no longer have the rights to use in sequels, why not keep the basic move set and use Nintendo clones as their stand-ins.
If Ryu can't come back, we could use Karate Joe or the Urban Champion.
Snake could be replaced by Andy or Sami.
I'm sure there's SOMEBODY from Fire Emblem who could take Cloud's place (I'm not too familiar with the series).
I can actually imagine a trailer for Sami starting with the heroes fighting and the box in the background, the camera slowly pulls in on the box, and she flips it over announcing "What? Were you expecting somebody else?"
Admittedly, copying Bayonetta and Pac-man might be a bit hard.
Cloud: Takamaru. (Just change neutral B to something like Greninja's s uncharged B
Pacman: Nester. Instead of Pacman related moves, give him Nintendo related references moves: Instead of Hydrant, throw a Bowling Ball, instead of throwing Fruit throw, make him throw Nintendo hardware. (Controller, Zapper, Power glove, Nes advantsge, ROB, etc) Instead of trampoline, he jumps off a Nintendo Power mat.
Bayo: I would honestly not miss this moveset.. at all. But maybe something like Dark Samus could pull off a Bayonetta?
Extra:
Wouldn't mind Ninten as the faster of the EB characters.
Either King Hippo or Doc Louis as the heavyweight Mac clone.
I would LOVE to see Medusa as an alternate Palutena, who could spawn her underworld army Minions instead of Palu's other specials.
V
Monoeye (Neutral B) Nimble flying minion that will randomly shoot.
Speknose (Side B) Slow unit that shoots projectile at nearest opponent.
Shemun (Down B) Ground unir that damages on bite.
Teleport (Up+B) same as Palutena's.
Or replace them with KI:U monsters that do appear un Smash Run, to lessen the effort.
Having her as a Summoner would be awesome and unique. Especially if it's a clone in it's normal attacks.