Alternate Costumes are incomplete at the moment (I'm only up to Ghirahim as of now) but this is basically what I feel we'll end up seeing, give or take a few characters. Fantasic template by GoldenYuiitusin, thank you for that. And now on to explanations.
Mario Newcomers: Toad and Bowser Jr. - Both very well liked characters with interesting moveset potential and popularity. I'm not the biggest fan of either, but I feel both are pretty likely. Honorable Mentions: Paper Mario, Rosalina
Zelda Newcomers: The only "real" new character here is Ghirahim, because of his popularity and current-ness from SS. Also, his moveset pretty much writes itself. And while I don't think that Impa will get her own slot, I do feel she's likely to take over Sheik's role, and simply use all of Sheik's old moves. Sheik her/himself is included as an Alt Costume though. Honorable Mentions: Groose, Vaati, Tingle
DK Newcomers: King K. Rool: Honestly, probably the most important character to the series next to DK and Diddy, loads of moveset potential, and also has the benefit of being a popular choice. I know that Dixie was in Yui's original one, but I just don't see her being in over K. Rool, nor do I see DK getting four reps. She is, however, Diddy's alt costume. Honorable Mentions: Dixie, Tiki Tong
Metroid Newcomers: Ridley. The most deserving character left out of Brawl's roster IMO. Do I need to say any more? Honorable Mentions (And very likely if Metroid gets more than 2 reps): Dark Samus, Adam Malkovich, Melissa Bergman
Kid Icarus Newcomers: Now this is what I don't understand. Kid Icarus is almost definitely getting a new rep, but everybody seems to think it'll be Palutena. Now, I know she's important, and that she can have a moveset made for her, but I really don't see her being more likely than Medusa, who's got moveset potential all over the place, plus the benefit of being a villain. Although, I'd much rather have Palutena than Dark Pit or that Magnus guy. Honorable Mentions: Palutena
Kirby Newcomers: Bandana Dee seems pretty likely to me, with an already made moveset, lots of popularity, and being the only other playable Kirby character left. He also has the benefit of having somewhat of a history with the series. Honorable Mentions: Dark Matter (Sword Matter)
Starfox Series: Krystal is kinda so-so with me, but I'd say she's more likely than not, with Sakurai being interested in her. This is especially likely if the rumors of Retro's Starfox are true. Honorable Mentions: None
F-Zero series: Captain Falcon's been alone for far too long, and IMO the only real choice for a second character is Goroh. He's already been an Assist Trophy, has been Falcon's rival since the original game, and has more than enough popularity to warrant his inclusion. One of the more likely newcomers, I think, even more so if we do end up getting that Wii-U F-Zero. Honorable mentions: Black Shadow, Pico
Pokemon Newcomers: Mewtwo and Zoroark are really the only good choices here. Mewtwo never should have left in the first place, and Zoroark is the posterchild of Gen 5, just like Lucario was. Sorry Victini fans, but I just really don't find him all that likely as anything but a Pokeball Pokemon. I also REALLY REALLY wanted to include Deoxys here, but he's admittedly not all that likely anymore. Honorable Mentions: Deoxys, Meowth, Darkrai
FE Newcomers: Roy isn't really a newcomer, per se, but I feel like he's pretty likely to return, especially with the rumors of his game being remade. Seeing as how much backlash there was over his removal, I don't think he'll be skipping out on this Smash title. Although admittedly, if I was to try and cut this roster down, he'd be one of the first few to go. Also, I don't know where else to put this, but Marth is probably gonna speak English now, considering that his game's now available in English. Honorable Mentions: Chrome, Sigurd
Other Newcomers
Isaac: Loads of moveset potential, tons of fan support, and the added bonus of having been an assist trophy.
Little Mac: One of the most likely newcomers, with a good pool of moves, an important series to Nintendo history, and plenty of popularity.
Saki: Sin and Punishment just got a revival recently, AND both the original game and its sequel were ported to the US AND he was already an assist trophy.
Mii: Nintendo's been putting Mii's into almost any multiplayer game for a while now, and with Mii's being a bigger part of it's repetoire than ever before, I'm expecting to be able to play as your Mii by the time this game rolls around.
Starfy/Stafy: Despite the confusion about his name, this star has a number of great games under his belt, and has the popularity and moveset to prove it. His lack of a more recent game may hurt his chances slightly, but I still feel he's very likely to be playable.
Megaman: Easily the most deserving 3rd Party left, I can't see Megaman NOT making it in unless Capcom decides to keep him out. And I honestly think the whole Megaman "trolling" business has been thrown WAY out of proportion, so I don't see them preventing his inclusion.
Sukapon: The WTF character of my roster, Sakurai's been trying to add Sukapon to Smash since SSB64, but continually keeps running into problems with the Rayman-esque fighter. I feel like by the time SSBU rolls around, he'll finally get to put him into the game.
Shulk: Xenoblade has had a huge debacle over it coming to the US with Project Rainfall as of late, and with Nintendo seeming to have realized that people REALLY like this game, it's pretty likely that they'll capitalize on its popularity, and put Shulk into Smash.
Whew. I'm not gonna go into alt costume discussion as of yet (I'll save that for when I'm done adding them in). But suffice it to say, some of these characters I'm hitting a brick wall coming up with Alt Costumes for though, so help would be appreciated. (Ex. Zoroark, Game and Watch, Shulk, ROB, etc.)