Let's see...
Smash 64 (1999) was the first game and introduced only the mascots/protagonists of their respective franchises.
Mario, Donkey Kong, Luigi, Link, and Samus debuted in the 1980s. Yoshi, Captain Falcon, Kirby, Fox, Ness, Pikachu, and Jigglypuff debuted in the 1990s.
Melee (2001) was the second game and introduced newcomers who are mostly sidekicks, villains, and damsels... and introduced three new franchises with their respective protagonists/mascots.
Mr. Game & Watch, Ice Climbers, Peach, Bowser, and Zelda debuted in the 1980s. Marth, Dr. Mario, Falco, Mewtwo, Young Link, Sheik, Ganondorf, and Pichu debuted in the 1990s. Roy is the only one who debuted in the 2000s.
Brawl (2008) was the third game and introduced many more newcomers who are mostly sidekicks and anti-heroes and new protagonists to pre-existing franchises... and introduced six new franchises with their respective protagonists/mascots.
R.O.B., Pit, and Snake debuted in the 1980s. Sonic, King Dedede, Wario, Meta Knight, Diddy Kong, Charizard, Squirtle, Ivysaur, and Wolf debuted in the 1990s. Pikmin & Olimar, Toon Link, Zero Suit Samus, Ike, Lucas, and Lucario debuted in the 2000s.
SSB4 (2014) is the fourth/fifth game(s) and introduced even more newcomers who are mostly protagonists/mascots and supporting characters from revived franchises and newer games from pre-existing franchises... and introduced eight new franchises with their respective protagonists/mascots.
Pac-Man, Little Mac, Duck Hunt, Palutena, and Mega Man debuted in the 1980s. Villager, Bowser Jr., Mii Fighters, Rosalina & Luma, and Wii Fit Trainer debuted in the 2000s. Shulk, Dark Pit, Robin, Lucina, and Greninja debuted in the 2010s.
I would expect SSB5 newcomers to be mostly from 2000s and 2010s... with a few from the 1980s and 1990s depending on whether they appear in newer games during 2010s or not. I personally believe that the reason people keep saying we are running out of Nintendo characters to add in Smash is because they themselves are running out of characters they personally grew up with to add in Smash. We are running out of popular/iconic Nintendo characters from the 1980s and 1990s... that's why we are getting more popular/iconic Nintendo characters from the 2000s and 2010s. Nintendo will never run out of characters to add in Smash.
For SSB5, let me give an estimated year it might come out... let's say... 2020? Sounds good, yeah? Anyway, I would keep my eye on major new games between 2014 and 2020, especially by Nintendo EAD, Intelligent Systems, HAL Laboratory, Pokemon Company, Retro Studios, and Monolith Soft... and especially if Miyamoto and/or Sakurai are involved... and especially new games for franchises that already have playable characters in Smash.
These are the games from 2014 I have my eye on...
Captain Toad: Treasure Tracker
Donkey Kong Country: Tropical Freeze
Hyrule Warriors
Kirby Triple Deluxe
NES Remix Pack
Pokemon Omega Ruby & Alpha Sapphire
Pushmo World
Wii Fit U
Wii Sports Club
These are the games from 2015 and onward I have my eye on...
Code Name: S.T.E.A.M.
Kirby and the Rainbow Curse
The Legend of Zelda: Majora's Mask 3D
The Legend of Zelda Wii U
Mario Maker
Project Giant Robot
Project Guard
Splatoon
Star Fox Wii U
Xenoblade Chronicles 3D
Xenoblade Chronicles X
Yoshi's Woolly World
If I were to come up with an incomplete list of possible newcomers based on 2014 and 2015 alone (which is too premature), these are who would be on my list... and they still would have debuted from different decades:
3rd gen Pokemon
Bandanna Dee
Captain Toad
Dixie Kong
Henry Fleming from Code Name S.T.E.A.M. (new series)
Inkling from Splatoon (new series)
Mallo from Pushmo (new series)
Protagonist from Xenoblade Chronicles X
Someone from Legend of Zelda Wii U
Someone from Star Fox Wii U
As for retro characters, I have my eye on Takamaru (I think his series might be revived before SSB5 is announced), Muddy Mole (I think he is a solid pick since Nintendo EAD was the developer and Miyamoto was the producer of his game), and Captain N (the next unlikely retro pick after G&W, ROB, and DHD and I think he will make headlines like DHD did).