I believe that Mega Man is one of the very few third-parties worthy of consideration for a guest slot and I'd argue that he is the best choice out there.
Mega Man, if included, would be not only a more popular addition than Snake but also potentially as popular as Sonic's addition was in Brawl. Now being possibly as popular as Sonic's addition was in Brawl may sound crazy given how high of a bar he set for third-parties (although it could be argued that Snake set the standard), but it is achievable.
Let's consider the two inclusions first; Snake and Sonic. Both were extremely well-received additions that were highly popular with the Smash community, so much so that Sakurai has commented positively on their inclusions. However, their inclusions were not perfect as they came with issues (aside from Sakurai infamously commenting on the incredible difficulties of adding third-parties).
It should go without saying that Snake was added because Kojima practically begged for Snake's inclusion in Melee and he was the one third-party that was always meant to be in the game. Like said in the OP, it was obvious that Snake was treated as that one special addition and it's really the special treatment Snake got that made him so popular within the Smash community. However, despite his inclusion generally being a success, there were inevitably issues with his inclusion. The first thing is really the type of games he comes from. Snake comes from a world that is practically alien to the Nintendo world; a realistic stealth genre. He also faced the issues of not being able to use his guns in the game as a rule from Sakurai. As such, it's obvious why including Snake was an excruciating progress; because putting Snake in a relatively cartoonish platform-fighting game is something that can easily ruin his character. It was so difficult that Snake required disjointed box in order to fit in. The fact that Snake even got to be in Brawl is a miracle (although we could say that the roster in general is a miracle). Another thing is that while a lot of people loved him, he also faced a lot of objections. There's the inevitable dissenters of third-parties, but another thing to take into consideration is that Snake is generally synonymous with Sony platforms. When people think of Snake, most don't think of the sub-par NES Metal Gears port, the Twin Snake Gamecube remake or the 3DS Snake's Eaters remake, they think of the Metal Gear Solid games on the PSX, PS2 and PS3. Now don't get me wrong here, Nintendo history isn't relevant to a character's chance (which is why I consider the news of Tales of Symphonia remake going to the PS3 irrelevant to Smash), but it's undeniable that a large part of the objection for Snake has to do with him being mostly well-known for his non-Nintendo games.
Sonic was obviously included because of him being by far the most wanted character. When he was included, the gaming community pretty much exploded that Sonic was finally in. Sonic was one of the very most popular characters in the game and even more popular than Snake was. He along with Snake set the bar for third-parties exceptionally high. Yet like Snake, Sonic's inclusion wasn't perfect either. What kept Sonic from being the "perfect" addition was the fact that he was added so late to the game. Now it is true that Sonic was the most wanted guest before E3 2006, but the fact remains that Sonic simply was never going to be popular enough to add in. Before E3 2006, Sonic wasn't even in the Top 10 (it really doesn't matter that Sonic's popularity wasn't at it's full potential due to us not knowing that third-parties are possible, the fact remains that Sonic's popularity wasn't enough to get him in at the time). When Sakurai already struck a deal with Snake, what would make people believe that he would go through a painstaking process to add a guest character that failed to break into the Top 10 and didn't have companies trying to get him in? E3 2006 with Snake's reveal changed all that. Sonic became by far the most wanted character and the rest is history. However, the result of Sonic being a late addition is shown as he received much less work on him, which is shown by Sonic having practically no role in SSE and that there were no original remixes for Sonic (whereas Metal Gear had some remixes done specifically for the game). There were also a ton of criticism in regards to Sonic's move set being bland. All of these were a result of Sonic being added at literally at the last minute and Sonic's inclusion, while a fantastic move, could be significantly improved upon. It's for this reason why I believe that giving Sonic the Snake treatment could merit his return because his inclusion wouldn't be stale then.
Over five years since Brawl's release and we are at the cusp of Smash 4's unveil. Guest are now accepted by almost everyone in the community and most third-parties supporters are rallying for Mega Man's inclusions. Mega Man to this date looks to be likely the most wanted newcomer for this game worldwide (Shortie's poll indicates that Mega Man beats every other potential newcomer whereas ChronoBound's observation indicates Mega Man as probably the most wanted newcomer in Japan). There are reasons to believe why Mega Man might get in despite the odds.
The first thing to consider is the fitting in issues. Snake's inclusion was especially hard because of the realistic stealth-genre he was placed into; which would stick out like a sore thumb if placed with other Nintendo series (and he did despite his inclusion in Brawl being successful). Mega Man fits much better within Nintendo's world than Snake does since his series is a cartoonish action-platform game; much like how Smash is a platform-fighting game. Mega Man could be placed with other Nintendo series and it'd be like he fits right in. Sonic had to deal with being added literally at the last minute, so they had relatively little time to implement Sonic. Mega Man, if included, would be added much earlier (and perhaps even from the start), giving Sakurai and the team much more time to implement Mega Man. While Mega Man would still remain an extremely difficult addition by third-party nature, adding him early on would make it easier on Sakurai than Snake or Sonic would.
Another thing to consider is that if Mega Man is going to reach the same caliber of popularity as Snake and (more importantly) Sonic in Smash, Mega Man is going to need the Snake treatment. In other words, like Sakurai did with Snake, he will have to do as much as he can to make Mega Man's inclusion worth it. Including Mega Man as a last-minute character would end up having the "diminishing marginal utility effect" that you expressed as a concern in your essay on why you doubted third-parties but planning Mega Man from the start and giving him the Snake treatment can potentially rectify that. It would likely avoid the bland move set complaints that plague Sonic and Mega Man's much more relatively orthodox would go over better than Snake (and likely avoid disjointed hitbox as well if done right).
Finally, and this is the reason why Mega Man is even being discussed as a candidate, his massive popularity. While it is not on the same level as Sonic, Mega Man still performs well. Being likely the most wanted newcomer does help and is a big advantage other every other third-party character. Another thing to consider is that not only is he one of the most wanted characters but also one of the longest-running characters. Sakurai himself has noted Mega Man's popularity all the way back to pre-Melee time when Sakurai commented on Mega Man receiving a lot of requests overseas. What this means is that Mega Man has been requested for over a decade; before even Sonic became a popular guest request. No other third-party character can claim being highly requested nowadays that was popular pre-Melee. As a matter of fact, Ridley is the only character that was popular pre-Melee that is highly popular today. Also take into account the past few years, which to put it mildly, have been extremely difficult times for the Blue Bomber. Of course these events definitely don't help Mega Man's chances, but these past few years really shows how strong of a character Mega Man is. With most fan base, they would have toppled and collapsed with people moving on to support other characters, but the opposite effect has taken for Mega Man. The support for Mega Man has instead increased. Supporters want Mega Man in not only because of Mega Man's character, but also because they want assurance that the franchise will continue and not go into obscurity. The fire that lit up the support of Mega Man for almost all of it's fans have not been extinguished, but rather burn even more intensely with even more joining in. Along with Mega Man's iconic status, Mega Man is indeed a strong character, even for the incredibly high guest standard.
Mega Man, if in, would be one of the biggest additions to the game. He is undoubtedly the biggest third-party left with a realistic shot of getting in and he'd make a bigger addition than any potential newcomer (only Mewtwo would end up being a bigger addition). As a character, Mega Man is indeed strong. Probably the most wanted newcomer and being wanted ever since pre-Melee, being a video game icon and likely being an easier fit than Snake and Sonic can make Mega Man as popular of an addition as Sonic and Snake were if given the same treatment Snake was.
Whenever or not Mega Man gets in is a different story. Like every third-party, Mega Man has his negatives and there's a good chance he won't get in. However, when it comes to new third-party additions, there is no one else that compares to Mega Man (although that's not to say he's the only good choice, just the best) and I do believe there is a very real chance that he gets added. I'm very curious about what happens with guests for the next game, but Sakurai could pick pretty much any possible options that doesn't force Pac-Man upon us (in which case it'd be better to get rid of guests all together) and he'd do a good job (Mega Man, Layton and a Tales rep I feel would all make solid additions, although I only really care about Mega Man).
