I thank you for going into more detail, but could you give me examples, please? The last heavily criticized Mario game I can recall is NSMB2, and I'm pretty sure it still sold very well. Also, the Sonic fanbase has been really touchy with recent Sonic games ever since Sonic 06.
I think being recognizable and significant to Nintendo's history are two important factors third parties really have to pay attention to, and Sonic excels in both of those areas. I personally like Mega Man way more than I like Sonic, but I wouldn't say that Mega Man deserves to get in before him.
That's the thing though, the fans have been incredibly forgiving of bad Sonic games. Most franchises would be lucky to even survive after a game like Sonic '06, let alone continue to get almost yearly installments. F-Zero GX was highly praised but sold terribly; the franchise is pretty much dead. The last three Star Fox were medicore at best; it's highly questionable if it'll ever come back. Megaman 10 didn't do as good as Capcom had hoped; franchise has been on an almost 4 year hiatus. Metroid Other M was panned by critics; Metroid will probably be shelved for another 2-3 years. Sonic releases Sonic Heroes, Shadow the Hedgehog, Sonic '06, Sonic and the Secret Rings, Sonic Unleashed, and Sonic and the Black Knight back to back and keeps making games annually. This stretch of bad games would have killed any other franchise and most dead franchises have been done in by a single bad game.
As a person who grew up during it, I think the SEGA and Nintendo wars of the early 90's are overblown. Was there a rivalry? Yes and it was pretty intense... for about 3 years, not the entirety of the SNES/Genesis era like some people think. SEGA had an edge on Nintendo from 1990 to 1993 and was able to match their big hits with games equally as great but around 1994, things really started to take off for Nintendo and produced arguably the three best years gaming has ever seen. Juggernauts like Super Metroid, the Donkey Kong Country Trilogy, Megaman X-X3, Yoshi's Island, Chrono Trigger, Final Fantasy III (VI), Kirby Superstar, Super Mario RPG, etc came out and SEGA really had no real answer to any of these. The SEGA CD didn't take off and the SEGA Saturn practically crashed and burned by the time the Playstation came around. By 1996, SEGA's future was already questionable. I'd argue that the rivalry between Nintendo and Sony was significantly more important especially when you consider how Nintendo initially lost a ton of its third party developers to it and made them realize that cartridges were becoming more and more obsolete with each passing year. Sony made Nintendo realize that the days of the NES and SNES were over and that they had to change their strategy or get left in the dust (and in some aspects they are still playing catch up to this day).
Sonic didn't really bring anything new to gaming as a whole like Megaman did. Two important things that Megaman brought to gaming were being able to choose your own path in games and "rock-paper-scissor" strategies not only when it came to beating bosses but also figuring out the best way to go through stages. This is especially significantly when you consider how most games back then were extremely linear. The Sonic games were a lot like the Mario games and used many of the same elements with the only real major difference being speed. The gameplay was faster but that wasn't something that really inspired other games as a whole. On this end, this is why I'd argue that Snake contributed more to gaming than Sonic and his inclusion in Smash Bros was a little more understandable. The Metal Gear franchise popularized the concept of stealth in gaming which, obviously, is a widespread concept in a lot of games now-a-days. Were the original Sonic games good? Yes and they are indeed classics but I'd be hard pressed to say that they were revolutionary.
Then there comes the matter of when SEGA actually started to work with Nintendo; 2002. Sonic was announced in Brawl in 2007. See the issue? Megaman had games with Nintendo since 1987 (with a vast majority of them being Nintendo exclusives until 1997, I might add). Bomberman since 1983. Even Snake had some games going back to 1987. It doesn't help that Sonic didn't really have any real console exclusives with Nintendo until the Wii with the first one being Sonic and the Secret Rings in early 2007 so, in that sense, Sonic only had a little more than half of a year and a single exclusive Nintendo console game before being admitted into a franchise that celebrated the history of Nintendo as a whole. When this all is considered, you see that Sonic pretty much got in because of his popularity. This isn't to completely discount the Sonic Advance series or the Sonic Rush games but it shows that Sonic hasn't had that much of a showing for Nintendo consoles as people give him credit for.