I've been lurking on this debate for a bit now and decided I might as well chime in. I've got a few points and a speculative character list to add.
WARNING! MASSIVE WALL OF TEXT!
1.) Why are we so heated over which characters to remove? Shouldn't we be more focused on trying to predict what characters will be added. Honestly, I believe that they only removed Mewtwo because of time restraints. He'll likely be back next game (IMO), but not at the expense of Jiggly or Lucario.
2.) I'm with Kuma that characters would likely be selected based on playstyle, not on what's "hip" in the Nintendo scene. How else do you explain Ice Climbers? Brawl isn't exclusively fanservice- it's a game in it's own right.
3.) I personally do believe it's a risk to bring Sakurai back due to his stance on how a game should be made; although I prefer Brawl to Melee, there were some things that were added or removed in Brawl that were an unnecessary waste of time and money (stickers and pratfalling, mainly). However, it's also a huge risk to bring in a new developer, as he may try to take the game in the wrong direction (too serious, too complex, etc) One thing I wholeheartedly agree on, though, is that the next developer should take the fans into consideration more.
And now, the speculative character list I came up with (just newcomers, since I already specified that there would be no removals)
Super Mario
-Bowser Jr.
-Paper Mario
Donkey Kong
-King K. Rool
Yoshi
-Kamek
The Legend of Zelda
-Redo of Ganondorf's movelist
Metroid
-Ridley
Star Fox
-Krystal
F-Zero
-Samurai Goroh
Pokemon
-Zoroark
Fire Emblem
-Micaiah
Custom Robo
-Ray MK
Duck Hunter
-Duck Hunter
Captain N: The Game Master
-Captain N
Sonic the Hedgehog
-Knuckles
Castlevania
-Simon Belmont
Megaman
-Megaman
Final Fantasy
-Black Mage
Now, some points about the list in general
1.) It's 17 characters, no need to count. For comparison, Melee added 13 characters, 1 of which had 1 alternate form, and 6 were clones. Brawl added 16, 1 of which was actually 3 characters, an alternate form was added, and 1 was a clone (I don't consider Wolf a clone, as he plays fairly differently from Fox and Falco) while removing 3 clones and 1 original character. So, moveset-wise, Melee added around 11 (counting clones as 1\2) and Brawl added 18.5 movesets. You may notice there's not that much of an increase. In fact, there's a decrease. That's so that focus can be added on the much-needed balance element (along with an improved singleplayer and definitely improved online)
2.) "OMG 4 NEW 3RD PARTIES THIS GUYS A ******!!!!" Yeah, there are a few reasons for that. One is that Brawl had (IMO) pretty poor 3rd party choices when it comes to their Nintendo-ness; Sega used to be Nintendo's rival company, while MGS was hardly ever associated with Nintendo. Although Knuckles falls under the same category of Sonic (he's just in there because of popularity and to give Sega a 2nd rep), Castlevania, Megaman, and early Final Fantasy are generally much more closely associated with Nintendo. Second is moveset potential, especially for Black Mage and Simon.
3.) No "new" LoZ characters. LoZ is my favorite Nintendo franchise, but there's no other major recurring characters left as of now except for Vaati, whom I've never really cared too much for.
Now here's some reasons I have for the individual characters;
Bowser Jr.- Very popular new character, has great moveset potential when armed with the paintbrush. Plus, Smash Bros. has a rather small rogue's gallery (consisting of only Bowser, Ganondorf, Wario, and Wolf in Brawl)
Paper Mario- A good rep of the RPG side of the Mario series, along with having good moveset potential due to his papery properties and fighting style consisting of hammers, aerial stunts, and partners.
King K. Rool- Again, Smash needs more villains. If his personality is kopied from DK64, it could result in some humorous antics in story mode as well. And his skills as both a projectile user and a boxer have moveset potential.
Kamek-I was trying to make all the original 10 series have more than 1 character in this set, and Kamek is the only other important Yoshi character other than (*gulp*) the Baby Mario Bros. Plus, yet another villain and I came up with a rather interesting moveset for him a while back that I could be persuaded to dig up.
Ganondorf redo- I and everyone who is even vaguely fond of the Zelda series that I know was pissed upon finding out the King of Evil was a Falcon clone. Being turned absolutely useless in Brawl was even worse. He has so much more potential with his combination of brutal swordfightning and black magic.
Ridley- Sorry about opening this particular can of worms, but it had to be done. He can be resized while remaining awesome. And besides, nothing worse can happen to him than Ganondorf in Brawl. Yet another villain and good moveset potential, especially since he'd likely be the largest and thus heaviest character in the game but would still be capable of flight.
Krystal- Moveset potential and shutting the fanboys up, mainly. Honestly, if 1 character from this list had to be cut, I'd pick her. Still, it would be interesting to see her moveset and it's always nice to have another character to appeal to girl gamers. Why her and not one of the other 2 fanboy-popular characters (Midna and Geno)? Both of them are 1-shot characters and Geno is owned by another company, and the licensing money would be better spent on a more popular character (Black Mage).
Samurai Goroh- Again, villains and original 10 rep. Plus, I'd like to see his fighting style, since he's a heavy guy fighting with a very light sword, while all the other heavy characters in the game wield heavy weapons.
Zoroark- Popular 5th gen rep. Great moveset potential with his focus on illusion as well.
Micaiah- Another female who is also a spellcaster. Plus, she's fairly popular and I believe the main hero of Radiant Dawn.
Ray MK- Moveset potential and adding a new Nintendo series so we'd have something other than retros and additions to other series.
Duck Hunter- Retro character along the lines of Ice Climbers or Pit. I originally considered Little Mac for this position, but Punch-Out! was recently revived and his fighting style would have been redundant with K. Rool. Anyhow, he'd have a pretty interesting moveset too, I'd imagine.
Captain N- A "WTF?!?!" character like Game & Watch and R.O.B. Can't think of much more to say.
Knuckles- Fan demand, mostly. I never played a Sonic game so I don't see much moveset potential, especially given Sonic's rather bland moveset in Brawl.
Simon Belmont- Hailing from one of the SNES's most popular games, Simon would add a very interesting personality and moveset to the game, as we have never had a true whip-fighter before, as Sheik only uses her whip for 1 attack and ZSS's whip doesn't operate like a "true" whip, as doesn't feature some whip characteristics (namely odd moving hitboxes and sweetspots).
Megaman- Again, never played a Megaman game, but he's pretty much synonymous with Nintendo's glory days. From the videos I've seen, he looks like he'd have a pretty cool moveset too.
Black Mage- Has appeared in quite a few past and present Nintendo games. We could use another spellcaster too.
Quite a few things are mispelled or just plain-out missing, but this was typed pretty hastily. Also, sorry about the wall of text.