Ephraim was mentioned a bunch of timesSome never-mentioned characters I came up with these days:
Ricky Winterborn (1080º / Wave Race): A character based on two modes, snowboarder and water scooter. I think it has material for a pretty original character.
Prince Ephraim (Fire Emblem): we have lots of sword based characters... but we haven't a lance based one. Long range, zoning character. Could fit PM perfectly.
Diskun (Famicom Disk System interface): not exactly a video game character, but it could use lots of retro references such as Pac-Man does in SSB4.
King Boo (Luigi's Mansion): we need a nemesis for Luigi. I think this character could be a defensive one. Very good at avoiding attacks and one interesting mechanic: if the enemy sees him, he is damn slow. So he must be with his back to the enemy in order to perform a quick combo.
Kyle Hide (Hotel Dusk / Last Window): a character from a graphic adventure is something I would kill for.