While I don't think your franchise has to be synonymous with Nintendo like Mega Man or Dragon Quest to get a playable chaaracter, I do think you need some sort of working relationship with the Big N and some kind of release on a Nintendo system to be eligible for Smash:
's impetus was Kojima going to Sakurai during Melee's development, but even then Metal Gear was not completely foreign to Nintendo. There was the NES port of Metal Gear 1, the America-only Metal Gear 2 for NES (although, I doubt this changed much), and Metal Gear: Ghost Babel on the GBC. Metal Gear Solid: The Twin Snakes would also release a Gamecube exclusive between Snake's proposal in Melee and his release in Brawl.
is largely an arcade icon, but he still had a few games on Nintendo systems. The NES port of the original Pac-Man, Pac-Attack for the SNES, Pac-Man 2: The New Adventures for the SNES, and the Gamecube ports of Pac-Man World 2 and 3 are all clear examples of this. Pac-Man had also crossed-over with Mario twice, once with Mario being the announcer in Pac-Man Vs. and Pac-Man being playable in Mario Kart GP.
is a lot like Pac-Man, he's mostly known for the arcades but still has a good number of Nintendo appearances. There were numerous SNES ports of Street Fighter II on the SNES and Game Boy, plus Super Street Fighter IV arguably being the 3DS' killer app on launch day.
is a tricky example. While's the face of Final Fantasy on Playstation, the fact Sakurai considered adding the Nintendo centric Bartz or Terra to Smash instead possibly suggests Cloud's Playstation affiliation may've been considered a hurdle to his inclusion. Final Fantasy still ultimately has strong ties to Nintendo, with the NES and SNES being the home of the first 6 entries and Nintendo handhelds seeing semi-frequent rereleases after that. It's likely this strong history with Nintendo was the basis for the inclusion of a FF character, rather than just a desire to see Cloud.
is another tricky example. Not counting Shin Megami Tensei, Persona's been Playstation exclusive since day 1. However, both Persona Q games did see a release on the 3DS and Atlus considers first one canon (no idea if the second one is though). Likewise, you can also turn to somewhat grey example of Shin Megami Tensei If, a SNES game that is technically part of the Shin Megami Tensei series that laid down the foundation for Persona, with many considering it a technical "Persona 0". There's also the Switch port of 5S: Strikers, although it's tough to tell if that had an influence.
is another arcade juggernaut that saw some ports on the SNES, but I think Terry's main connection to Nintendo was SNK's all-in approach to supporting the Switch early in its life. SNK's Neo Geo ports were a massive help in filling the Switch's e-shop for the first few months of the console's life and this strong support to the Switch helped spur the talks that would get Terry in Smash.