The general consensus is that Sonic will return. I don't think anyone would dispute that. If they were to add another from the Sonic IP, I think Knuckles would be the most logical. He'd be able to have a different moveset from Sonic, while still having a glide ability that would be more accurate to the character without breaking something like Tails and his ability to fly might do.
I don't see any reason Snake couldn't return either. While his inclusion in Brawl was quite left field, he quickly became a beloved character just because of his difference in playstyle from any of the previous characters that had been made to that point.
As for new characters, I'd like to see Lloyd and Regal from Tales of Symphonia. ToS was a great selling game on the GC, and was made by Namco as well. And as has been shown so far w/ MegaMan's moveset, they would be able to add a lot gameplay-wise based on the way they fight.
Lloyd would be the first dual-swordsman in the series. With the two-handed swords being his main mode of fighting, his B-Moves would be a variety of the artes he had in ToS. Up-B could be the Tempest attack(would go up and at an angle), B could be Demon Fang, etc. Some of the A attacks could be taken from those moves as well.
Regal, again as shown with MegaMan, would change up how he fights even more mainly because he wouldn't use his hands for fighting(as they'd be in handcuffs of course). Just the sheer "Whoa that's awesome!"ness of his fighting style would make him a fun inclusion. I choose the two of them because they'd both be melee-oriented characters with visuals that would be different from the standard array, and their abilities would be easier to transcribe into the game than say Sheena or Collette would.
I'm sure there are a million reasons these ideas could be ripped apart, but its what I'd like to see.