1. Skull Kid - has possibly the most creative potential for a newcomer, being an amalgamation of Lovecraftian horror, magic trickster, and fairy tale scarecrow that does a good job representing Zelda's non-human characters (which there are so many of, and so poorly represented.
2. Paper Mario - moveset potential galore, and probably the last major Nintendo ongoing franchise (probably excluding Rhythm Heaven) yet to be represented. Would also be an easy character to make, as he would require a lot less animation work than other characters, similar to Game & Watch. Lots of rich history to pull from.
3. Tetra - people tend to count her out, and I can't for the life of me see why. Probably the most expressive character in Zelda, a PIRATE (which Smash doesn't really have any of - Rool only turns into one for a single move), one of the more commonly known and acclaimed Zelda characters in Japan, a character Sakurai himself worked to include in Smash Bros a little earlier, lots of attention leading up to the '15 ballot, great moveset potential, one of the most recurring characters in Legend of Zelda games period, and looks nothing like any of the other Smash Bros. characters. Would also even out the look of the Zelda roster so far with more fun and flair, as it is starting to looking a little super-serious and Fire Emblem-y. The Pirate Ship needs its captain!