Per franchise, here is who I feel best fit a newcomers from who we know now. Not saying that a sizable number of these will be in the Smash 4 or even Smash 5 roster, but here is who I feel are the "next biggest" for the franchises.
Mario: Bowser Jr., Paper Mario, Geno (..I Hope)
Donkey Kong: Dixie, Cranky, King K.Rool
Yoshi: Kamek, Baby Bros.
Wario: Ashley, Waluigi (rebranded Wario character as of this game)
Legend of Zelda: Tetra, Impa
Kirby: Bandanna Dee, Adeline (BIG stretch for her)
Star Fox: Krystal
F-Zero: If a new game actually comes out in the next 5 years, Black Shadow
Metroid: None, until we get a recurring character who doesn't fit best as a boss.
Kid Icarus: Medusa, Dark Pit (Anti-clone, looks similar but plays almost entirely differently)
Pokemon: Sceptile, Gen 7/8 Starter or Movie-Important character who the fans love.
Fire Emblem: Anna (character in all games except Gaiden), a proper Spear or Axe user who is key to the story.
Earthbound: Kumatora, maybe Masked Man.
One-Character-Per-Franchise Series: Isaac (Golden Sun), Ray (Custom Robo), Marshal/ChorusMen (Rhythm Heaven)
Xenoblade(?): Important ally of X or a third game (as long as the series remains popular)
Sega: Dr. Eggman, Nights
Capcom: Zero, Ama-/Chibi-terasu, Pheonix Wright.
Konami: Simon Belmont/OtherCastlevaniaProtagonist
Other Third Party Companies: Square Enix is likely the next one to have a character put in.. I'm hoping for someone quirky like Cactuar or Moogle. Besides S-E, probably Platinum games (who often work alongside Sega and Nintendo) who have given the WiiU the work that a lot of third party teams have been avoiding... for this gen it'd be Wonder Red (deconfirmed probably due to the trophy) but we don't know who for the next game.