With the reveal of Lucina in particular, I'm now convinced that there are not two but three catagories to consider; starters, unlockables, and secrets. Unlockables are characters that have some condition to unlock but are not secret, that is to say they feature in advertising prominently despite not being initially available. These characters will likely be pretty easy to unlock. Secret characters are characters we will not be seeing before release and will be more difficult to unlock.
With that being said, I think the starting roster will be:
Pit, Bowser, Pikachu, Fox, Kirby, Wii Fit Trainer, Samus, Link, DK, Mario, Villager, Olimar(?), Peach, Marth, Zelda, King D3, Little Mac, Diddy Kong, Zero Suit Samus(?), Sheik(?), Yoshi, Charizard, Greninja(?), Miis, Ike, Captain Falcon(?), and potentially other unrevealed characters.
Unlockables will be;
Megaman, Luigi, TLink, Sonic, Rosalina&Luma, Lucario(?), Palutena, Pac-man, Lucina, Robin, and potentially other unrevealed characters.
Why do I think these characters will be unlockable? A variety of reasons. Note that question marks means I was unsure of myself when I listed them as such.
My reasoning is that it is good design sense to have more complex and harder to use characters become available as players prove themselves capable of using simpler, more instinctive characters. Note here that I'm talking about skill floor, not skill ceiling. While it's true that Melee fox has a seemingly infinite skill ceiling, being decent-to-good-enough at him isn't a hugely arduous process; he is unarguably much simpler to play than, say, Olimar. Olimar himself is an oddity; I fully expected him to be a locked character, but it seems Nintendo wanted to show off their one new franchise in Brawl quickly. However with this Smash bringing in a wide variety of new, complex characters to preexisting series, I think some of them will be locked on first playing. Previous smash games have done this to some degree; in 64 Ness had the most complex recovery and jump, jigglypuff specials are not intuitive in how to use them, and Captain Falcon requires a large degree of technical skill and speed to play as.
This does not necessarily line up with every single character I've put as unlockable; 3rd parties have a precedent to being unlockable as well, and clone-ish characters have never been part of the starting line up. Luigi, TLink, and Lucina are now in that mix as well. Zamus and Shiek I have no idea, I'm going on pure instinct. Olimar I believe should be locked but won't be. RosaLuma's puppetry will be very difficult for first time players, as will keeping track of however Robin's tomb system works. Lucario's aura system now makes a lot of his moves change properties over time, something a first time player might have a little trouble with, especially that recovery. Palutena's massively customizable moveset screams 'fun toy to unlock but too unpredictable in game to game fighting for early on'.
This also leaves us with a starting roster of at least 26, although I'm betting closer to 30: I think we'll see Wario at least join the starting roster, maybe a few others as well.
Secret characters are the bizarre, what on earth am I unlocking, too weird/crazy to be real stuff. Dr. Mario, Mr. G&W, R.O.B., and Ridley (if he's playable) would all strike me as strong options for this. Another new retro character is something else to keep an eye on, as are otherwise unplayable villains. Once again, Ridley, but also K.Rool, Ganondorf, and Wolf. Do they really count as secret if they're in previous games? I think so, I think there will be no hint they are in Smash 4 other than their previous inclusion to other games. I could also see Ridley making the jump to unlockable, although I cannot imagine a universe in which he's part of the starting roster. Another strong contender for this catagory is Dark Pit; seeing Lucina as a clone or semi-clone today makes me convinced they're adding new clones, in which case Dark Pit seems like a logical choice.
TL:DR; Starting roster of Pit, Bowser, Pikachu, Fox, Kirby, Wii Fit Trainer, Samus, Link, DK, Mario, Villager, Olimar(?), Peach, Marth, Zelda, King D3, Little Mac, Diddy Kong, Zero Suit Samus(?), Sheik(?), Yoshi, Charizard, Greninja(?), Miis, Ike, Captain Falcon(?), and potentially other unrevealed characters.
