I'm not sure if Sony would have the line-up to make a Smash Bros.-like game in 1999 or 2000 unless they immediately included third party characters. (their main first party titles from back then seem to be Ape Escape, MediEvil, PaRappa the Rapper, Twisted Metal, and Tomba, though I'm not too familiar with Playstation's history and I'm not sure if Crash and Spyro were first party for their first few games)
Sega, on the other hand? Hoo boy. Sonic (maybe a few other Sonic characters like Tails and Knuckles), Alex Kidd, Virtua Fighter, Shinobi, Shenmue, Shining Force, Gunstar Heroes, Streets of Rage, Golden Axe, NiGHTS, Phantasy Star, that car from Fighters MegaMix... I'm probably just scratching the surface here, and that's just first party titles. Plus, they could have Perfect Chaos or Segata Sanshiro (who would, obviously, be too overpowered to be playable) as a final boss unless they wanted to make a new character.
EDIT: and that's just for the first game! Sequels could bring in Yakuza, Bayonetta, Persona 5 if they still buy Atlus...