I can speak to the Sheik matchup, having played against quite a few very good Sheiks as Mega Man.
Mega Man can give Sheik a hard time because he has range and good trap potential. He can pretty easily get a Metal Blade in hand or Leaf Shield up during footsies, and both give him solid offensive and defensive options. If he has one of these and shields a hit from Sheik, he pretty much has a guaranteed grab, and grab -> pummel -> throw is probably Mega Man's best DPS, so he doesn't mind that at all.
Bouncing Fish can be risky because MM's fsmash has such range. Against good MM play, Sheik needs to always weigh the possibility of the MM perfect pivoting, dashing back well out of her BF range, and punishing with a pivot fsmash. Sheik also has to be careful with her aerial approaches, as Mega Man has some pretty solid antiair options (in order of strength, I'd say these are Danger Wrap if customs on, SHFF uair, running usmash, utilt or dsmash if you're feeling ballsy.) His standing grab range is ridiculously good so it can be surprisingly tough to space attacks against him when he is shielding.
Mega Man is also one of the few characters capable of making Sheik's offstage game hard. I've trapped many greedy Sheiks using Crash Bomber when returning to the stage. MM can attach Crash Bomb to the stage, bait out a gimp attempt by the Sheik, avoid it or ledge tech the hit, safely recover back to the ledge, then laugh as the Crash Bomb stage spikes her. Sheik also has to be wary of Leaf Shield when returning to the stage -- if MM has LS up and either shields near the ledge or ledge hogs, the leaves will often stuff her before she grabs the ledge, even if she uses BF or Vanish to get there. MM can then follow up by running off stage into a footstool, bair, of dair before she can Vanish back up. If customs are on, Danger Wrap can make offstage hell for Sheik as well.
Sheik's strengths in this matchup are her needles, grenades, and fast movement. Needles can interrupt Mega Man's flow, and if he gets a MB in hand and throws/z-drops it, Sheik can use needles to knock it out of the sky. Grenades will cancel and punish even a fully charged fsmash, IIRC, which is great for Sheik-- though if she mispredicts, Mega Man can get in on her and punish hard. And simply by moving around constantly and unpredictably, Sheik can make it harder for MM to land his Metal Blade -> utilt combo, which is one of his favorite kill setups.
Sheik's best gameplan in the matchup is just to get in MM's face and never give him the time or space to set up with MB or LS. When MM gets rushed down and panics he'll often go for the shield grab, as that's generally his best and safest option at close range. Sheik can bait that out and punish by fast falling out of range and then hitting him with a dash attack or grab. Because Mega Man is heavy this is often all she needs to set up a damaging combo string at low percents. (MM can UpB away to reset at mid-to-high percents.)
Overall, I find this matchup often ends up being a knockdown drag out fight, with both characters living to high percents and struggling to get a KO. Both characters have ways to pepper each other with damage, allowing them to slowly chip away at each other over the course of match; both can combo each other at low percents but have more and more trouble doing that at higher percents; both have solid camping options and don't have to approach if they don't want to; and both can punish each other's whiffed KO moves hard, which can make both the MM and Sheik players wary of throwing out unsafe moves unless they are absolutely certain they will hit.
For Sheik, most stocks end with Mega Man getting a kill throw (his bthrow), a SHFF uair kill, a fsmash punish kill on whiffed BF, a MB -> utilt kill on whiffed dash attack/grab, or an offstage kill with bair. For Mega Man, most stocks end when Sheik gets a successful read/punish with fsmash/BF, or stage spikes him offstage with bair or BF. She can sometimes get him with uair or offstage fair, but that can be tough to pull off because MM can very quickly get out of the way using his UpB, or fake her out with a b-reversed NeutralB or DownB.
I'd say it's even. I don't think there's anything that skews the matchup decidedly in one character's favor. Both have pretty solid options, and both have weaknesses that the other can take advantage of. I actually really enjoy fighting Sheik, as it often ends up being a VERY mind game intensive match.
