The only NES fighting game that wasn't a bootleg that had multiple selectable characters are TMNT Tournament Fighters and Joy Mech Fight. Those had 7 characters and 8 characters, respectively, but with some stipulations. TMNT has 4 characters that have similar sprites, and the last character (The Shredder) was a boss. Joy Mech Fight started you out with Sukapon, and had you unlock the others as you went along, not to mention that they all have relatively simple sprites with the floating limbs thing done as sort of a work around.
SSBNES
That all said, I feel like what is feasible is this: 1990 release. The idea of a Nintendo crossover already has floated around due to Captain N. Some big boss brings a few of the biggest Nintendo stars around to fight in a tournament. We'll have...
Donkey Kong Jr.
and the boss.
Mario is obvious, you can base Luigi off of Mario around this time, DK Jr. is here over DK for now because he was more of a protagonist, and they did that in the first Mario Kart, so it's not too farfetched, Link, Samus, and Pit are other big stars of the NES at the time, as well.
From there, I think things could end up somewhat differently. SNES, you could either see traditional 2D sprites or digitized sprites, ala Donkey Kong Country, Super Mario RPG, or Killer Instinct. If they assign Rare to it and co-develop with them, I can see them reusing their DK model, and maybe someone from KI as well, either Jago, Orchid, or Fulgore. If Nintendo wanted to make an earlier version, it could be released earlier in the console's lifespan, and that version would most likely have 2D sprites. Here's two versions, 1993 and 1996.
SSBSNES
1993
DK Jr.
[DK Jr. stays because of the Mario Kart thing, Yoshi is the big new side character who later goes on to get his own spin-offs, and was prominent enough to be a big side-character in the Super Mario World cartoon, Captain Falcon is from one of the first big releases for the SNES, and, IIRC, he was intended as a SNES specific mascot. Unfortunately, given Pit's lesser prominence, around this time, I can't see him making it back just yet.]
+ four bosses, 3 being unlockable
Ganon [pig]
[classic version], and the big boss
This is essentially the format of Street Fighter II's roster before later updates.
1996
Black Orchid
+ 4 Bosses, 3 unlockable: Fulgore,
, Pig Ganon, and the big boss
Donkey Kong Country and Yoshi being a prominent character (Yoshi's Island) are ingrained at this point. Black Orchid is my choice from KI initially because she stands out for being a female protagonist over the more basic Jago, and we already have a robot-looking character with Samus. If one non-RARE third party character were to get in, it'd likely be
. It's not too unlikely, given that Captain N had him.
Pre-SSB64, we might also get an updated "Gold" version of this game on the N64, though this version also interferes with Killer Instinct 2/Gold given that, in our timeline, that comes out in 1996. Maybe this project takes its place and a more 3D Killer Instinct [one that looks along the lines of Tekken or Soul Calibur] might come out later for Nintendo 64, as well as...
SSB64
Given that this is the third iteration, rather than the first, I agree that it'd be given more of a budget, priority, and development. Every original character would be back as playable, except maybe Pit. For who I think would be added, looking at the N64's games, and some selections like Mario Kart and Mario Party, I think...
...are fairly obvious additions. Wario would be more similar to his Smash Remix iteration around this time. Another Pokemon could also get in, though I'm undecided between Jigglypuff, Meowth, and Mewtwo. Mewtwo makes sense if we're going with the tradition of unlockable boss villains at this point. Plus if Ness still got in, you could base some of their projectile effects off of each other, potentially.
In addition, given that in one version Rare got pretty involved, I think
could also make it in. Unfortunately, around this time, I can't see Mega Man getting in as easily. While CAPCOM did release a version of Legends, most of their support was on the PlayStation and Saturn/Dreamcast around this time. However, Hudson and Bomberman were pretty prominent around this point, to the point of Hudson developing Mario Party games, so if any other third party got in, it'd be the White Bomber.
This roster overall could be between 17 - 21 characters in total, depending on how things go. Maybe a bit excessive, but Tekken 2, around the same time, did have around 23.
SSBGCN
What once was Melee would now be the fourth game. Maybe due to being so ingrained with Nintendo at this point, Rare doesn't get sold. If they don't, you could see Conker or Joanna Dark join the game. If Microsoft still does own Rare at this point, however, there are still some pretty good additions to be made.
-A third Pokémon, either Jigglypuff, Meowth, and Mewtwo, depending on who is chosen in the last game, or potentially Charizard and/or Blastoise over any of those three, and/or a second or third generation Pokémon, depending on when in the GameCube's life this is developed and released.
-Marth and possibly another Fire Emblem character, given that Fire Emblem would either be out internationally, or is about to be. Could stick with Roy for an easy clone, or Ike if it's released really late, or Lyn or Hector, given that their game introduces the West to Fire Emblem.
-A second and/or third Kirby character, definitely Meta Knight or King Dedede still.
-Diddy Kong. No "and/or" here. Maybe he could be duo'd up with Dixie Kong.
-Olimar and/or Villager. New IPs. Andy or Isaac could also maybe happen, but it seems like they put more promotional stock in these two.
-Pit comes back, given the want to add an NES character. If you want a new one, the main other options are probably the Duck Hunt Dog & Duck, ExciteBiker, or Little Mac, given their relative prominence, though we might still end up with the Ice Climbers. Who knows?
-Mr. Game & Watch. Game & Watch Gallery makes him surprisingly relevant.
-Sonic the Hedgehog. For game 4, and for an era that also included Link in Soul Calibur II, as well as Sonic appearing on Nintendo consoles? This isn't too out of the realm of possibility.
-Pac-Man and/or a Soul Calibur rep. Speaking of Link's appearance there, maybe we can also see an earlier one of Namco-Bandai in Smash. Pac-Man is their biggest character, and a big character in gaming overall, but perhaps we could also see Nightmare come to Smash to return the SC2 favor.
Mega Man could also potentially return if he was a veteran previously, since CAPCOM seemed to start releasing more games on Nintendo consoles again around this point. Young Link or Toon Link and Falco or Wolf also might happen, since they're relatively easy to implement.
This roster could add between 9 to 20 characters, which could make the roster slightly surpass Melee's number or start to even approach Brawl's.
SSBW
At this point, I'd say anybody I said in the last one that I didn't say was in for sure could get in now, short of a second or third gen Pokemon at this point, the second FE character if it's Roy or Lyn if they weren't in already, and the Soul Calibur character. Let's say our first newcomers from last game's potential rejects are:
-
[since he's so associated with this installment in our timeline]
-
[since Sakurai had second thoughts at first, but then revisited them a game later]
-
[since he got a new game on this console, though whether it comes before or after this is anyone's guess in this timeline.]
For newer additions, we could see...
-
[most prominent and promoted 4th gen Pokémon]
-
[his Mario Kart addition makes this still plausible]
-
or
[depends on whether we have the Sakurai/Kojima friendship or if Nintendo and Konami decided to go with the series that had more Nintendo history. Plus hey, you could have all the Captain N team members that originate in video games. Aside from the Game Boy, I suppose. This also possibly depends on whether or not Konami owns HudsonSoft at this point.]
From this point on, I can't give you much variance on the other Smash rosters, and this is a big post already. If Pac-Man's in earlier, you could possibly see Kazuya or Nightmare in Wii U/3DS's DLC alongside Ryu, instead of Pac-Man being a new reveal there. You might see Black Orchid, Fulgore, Banjo & Kazooie, Conker, and/or Joanna Dark as another big sell on "Everyone is Here!" And because of that, you might also see Crash or Rayman in Banjo's place in the first Fighters Pass. Beyond that, not much more to say for now.