edit: accidentally touched submit on phone...
1. Megaman - I never played any of his games before but I know he is a popular third party charcter. He and Bomberman (a character I do know and hope for in future Smash titles!) are old iconic video game characters that aren't as popular as they were in the past so its awesome for them to appear in a popular game like Smash Bros and duking it out with Mario, Sonic, and Link.
2. Little Mac - I played some Punch Out on my laptop NES emulator and this game has aged pretty well for what it is - a fun arcade boxing game that requires the player to find his opponent's weak points and attack and dodge at proper timing. It make a lot of sense to have classic fighter like Little Mac to enter a fighting game like Smash Bros. and it's about time he appeared in SSB4! Because of these reason, I think he's the second best newcomer so far.
3. Rosalina and Luma - Mario Galaxy is one of the best 3D Mario games I have played (haven't played the sequel or 3D World yet) and I argue it has one of the most deepest story in the game. Ironically the story is not the main one (saving Peach) but Rosalina's storybook. The art style of her story book highly resembles the Little Prince, which is one of my favorite children books, and it was unexpectedly emotional and sad just like the Little Prince as well. Because of this, I think Rosalina is an awesome character for mirorring a popular literary character and I'm glad Sakurai thought of a way to make her a fighter too! Now give Rosalina a yellow scarf like the one the Prince wears for her alternative costume and I'll buy two copies of this game!
4. Wii Fit Trainer -what an unexpected surprise... and by unexpected, I mean completely expected! Just kidding. But in hindsight, how can one not see her (and him I guess) as a character? She's fit, does yoga, and body builds too, and her stances, poese, and mini games offers the Smash team a variety of choices to pick for an attack. And the Wii Fit games were huge last gen! Can't wait to do warrior poses in Smash Bros!
5. Animal Crossing Villager - Remember how popular this guy was? If not, here's a link that tracks meme activity and popularity. For the longest time people were joking about how Megaman, a favorite third party character, was getting his spotlight taken by this sprightly Villager. Turns out this Villager had an unexpected dark side we never expected until his pupil shined in delight as he captured Mario's head with his net. The Horror will continue this year hopefully!