I think the thing that hurts Mega Man the most (from what experience I have with him) is his real lack of threatening horizontal space control. Mega Man has plenty of options that travel horizontally in front of him, but very few of them are really dangerous.
The interesting part of this is that Mega Man's bullets, his basic horizontal control tool, are not only probably the least threatening option, but somehow an incredibly core part of his gameplay. I think the best style (right now) for Mega Man is to be extremely annoying and bullets fit right into this style. Bullets are unlike other projectiles mostly because of the low stun and medium range.
Consider lasers: they're coming from one of two ranges (generally) and the follow up conditions are extremely predictable. Lasers will either come from full screen followed by another laser or lasers will come from mid-screen followed by a dash up offense. The low stun on bullets means that you're not in any REAL danger by getting nicked by one, which makes the move really tempting to disrespect. The range, however, is brilliant because they travel almost the perfect distance to avoid roll retaliation and out of shield up smashes. The follow up factor is also much less predictable with bullets because all three can come out or maybe just one or two and any number of them can be followed up with Mega Man's short or full hop forward air for a "moving wall" sort of tactic.
With all that said, the point I'm trying to make is that disrespecting Mega Man is easy until he starts playing games with the bullets. While it's not threatening, Mega Man can use bullet tactics to really make the enemy dance to his tune even if just for a short while. I think smart plays against Mega Man will involve going in hard until Mega Man is capable of showing that he can make that close range wall that Yoshi typically has trouble with; I think this matchup is one of those "player" matchups instead of a matchup strictly based on the character. If Mega Man doesn't have a strong wall/bullet game, the idea is to really dominate the area in front of his face because he has no real convincing ways to deal with Yoshi there that don't entail some serious risk.
Yoshi really has to bully Mega Man by taking advantage of Mega Man's first big commitment mistake and very calmly stay in Mega Man's area. While I don't see too much down smash, I have seen up smashes mashed out during gaps in peoples' offense and this is probably one of Mega Man's better moves in my experience. I recommend staying aware of Mega Man's up smash range (test it out in Training mode); I think it's a pretty good defensive tool when people are just pressing buttons in Mega Man's face.
The tables turn a bit when Mega Man is edgeguarding Yoshi. Wind-based moves like up air (very similar to Gale Boomerang) can really mess with Yoshi's double jump recovery and while Mega Man can't really punish Yoshi for catching Metal Blade projectiles, he will likely use it and Crash Bomb to just give Yoshi another thing to have to react to while recovering. Back air is nasty--I think that's the most dangerous move in this situation overall and Mega Man's will likely be fresh if he doesn't have a super aggressive playstyle. It should go without saying, but learning to egg just under the edge while recovering (if your opponent is committing to an edgeguard move on the stage) is key for snapping to the edge; you don't want to double jump into a ranged forward smash at any percentage.
Mega Man really makes Yoshi work his normals out in this matchup. The B button will get very little love just because there aren't too many reasons to press many of them, I think. Get very comfortable with forward tilt (and its up angled version) especially.
Hmmm, what else. I guess I'll list what I think are problem moves from Mega Man and the situations in which they apply.
Back air (edgeguarding)
Forward smash (edgeguarding)
Neutral air [one shot] (sloppy aerial approach from Yoshi)
Up smash (sloppy ground or low altitude approach from Yoshi)
Forward air (basic retreating or advancing walling tool)