When it comes to Mario matches, it really depends on the type of Mario you're going against. I find the most irritating Mario players to be the ones that weave through your zoning and get damage any way possible. The ones that focus on trying to out-zone you seem to be much easier to deal with.
This is the matchup in which you really need to focus on keeping the opponent out, zoning as much as possible. Use pellets frequently, but try not to get predictable with them and make sure to mix up as much as you can. Often, Marios will try to jump in at you since a direct approach is tough for them. Tossing Metal Blades upward at an angle can stifle this approach, or make them airdodge for a punish. You can also mess their approach up with an Air Shooter if they're not expecting it, but be careful or it'll get Caped back at you and do a decent amount of damage. Often when Mario approaches using a full hop, he'll use down air (at least in my experience)...if they mess this up there's a bit of lag when they hit the ground that you can punish. Alternatively, you can do a quick pivot grab and usually snag them out of the attack.
If I use F-Smash in this matchup, it's extremely rarely, never charged, and after the opponent has been conditioned to not expect it. Focus more on movement and pellets rather than going for strong attacks as Mario is too quick for them.
If you see Mario use a Smash attack and you WANT to go in for a grab punish or something, back off instead. Mario's quick frame data makes it extremely hard to punish him on Smash attacks for Mega Man, particularly with our low run speed, so don't go in for anything. It's hard to remember at the time, but basically use that time to gain some ground and re-establish neutral.
Mario will often try to reflect blades back at you, but it's not much to worry about since you can just shoot them out of the air. Same goes for Crash Bombs.
When Mario is off-stage...I'm never sure what to do. Sometimes I go out for the gimp, which is with Slash Claw in this matchup since you do not want to get any closer to Mario than you have to. Fair is OK, but I find it risky and sometimes leads to a gutsy Mario landing a F-air if it's not timed perfectly. I don't go for N-air gimps either, due to the fact that you need to get close. Leafstooling doesn't seem to be an option close to the stage once he begins his Up-B, so if you're going to go for it you have to move out pretty far. Instead, I will z-drop blades, throw blades to try and catch Mario, or get a Leaf Shield up while I'm waiting on stage. In some cases, Mario being hit by Leaf Shield will result in an input error, causing him to Up-B the wrong way and die...and in others, he will Up+B with the wrong timing and won't grab the ledge, leading to further punishment such as a grab or a Spark Shock. You could jump out and throw a Crash Bomb on the corner of the stage too if you want, to force certain options out of your opponent...just make sure you have time to get it set up.
If you land a grab on Mario, go for safe options. D-throw -> Fair is always good, but you can sometimes get D-throw > Bair > Bair as well which racks up around 30 damage. You can also throw him upwards and set up for Air Shooters, but just be wary of his ability to reflect them.
If Mario lands a grab on you...you're gonna eat a lot of damage and possibly lose a stock. He can dthrow > uptilt us for a while (usually 3-5 uptilts) at low percent, and then start throwing in upair strings which Mega Man falls into pretty easily. DI out of it as best you can (I usually DI up and away) and bust out Rush as soon as possible to get distance and hopefully get back to neutral game. Alternatively, if you are quick enough and at super low percent, you can DI down toward the ground. In this case, Mario will usually land 1-2 uptilts and then you'll get to the ground and shield...and in true Mario fashion, he will spam 1 or 2 more uptilts. You can punish this with a grab of your own and hopefully land some damage, or you can also throw out a Mega Upper. The Upper is mostly for mindgames I find. If a Mario knows that you can potentially land a kill move in between their uptilts, they might not go for that option as much.
I never go for Z1gma Upper in this matchup because it seems like Mario's too quick to land it on in a lot of cases...and even if you get the blade out, he can reflect it very quickly. A blade directly down might work better since he often needs to be up close. If they shield it, be wary of a grab and back off instead, because if Mario lands a grab on you out of shield, you're in a bad way.
Mario can put himself out there for a gimp on Mega Man pretty easily since he's got good jumping power and air speed. Watch your opponent carefully when he does this. Often, Mario will go for bairs or nairs to gimp us; we can outrange both of these with our Slash Claw. When you're coming back to the stage, try turning around by shooting a Crash Bomb backwards, which will set you up to challenge Mario's Bair with your own. Also, if you land a Crash Bomb on Mario while he's waiting to gimp you, it will force the player to stop and react to avoid damage. Take this time to get up safely. Another option is to equip yourself with a blade on the way back to the stage. When you're falling at normal speed, toss a blade downward and Z-grab it. This at least gives you a quicker projectile option than Crash Bomb, and even a mixup if you Z-drop it again and go for something else.
Don't hang on the ledge too long, or Mario will use his stupid dash attack and stage spike you. They might try to 2-frame you with it as well, so be careful and watch for the move.
Sometimes you can Hard Knuckle Mario out of his Up-B, other times you can't. I find it too unreliable to go for it frequently, and instead opt to set things up on stage with Leaf Shield and a Metal Blade. I also don't find it worthwhile to go out for the stage spike on Mario. If you want to Ledge Trump, stay back a bit so he doesn't hit you with the final frames of his jump punch, or trump by coming down from the air. It will be tricky though.
Oh, and don't worry about being gimped by Cape. When Mega Man gets hit with the Cape, it gives him his Rush Coil back
Avoid Battlefield and Dreamland like the plague (although Dreamland is better if you have to choose between them). Their platform setup is heaven for Mario combos which can sometimes just outright lead to your death. Duck Hunt will allow you to survive longer against his Smash attacks if they catch you, and Town & City can sometimes lead to some early Air Shooter kills. FD is good as well. Do your best to play 'Stay Away From the Plumber', and go for the safe punishes whenever you can.
Those are just some thoughts for now. There is a really good Mario player in my region and so I have a decent amount of experience against an aggro Mario user. It's not an easy matchup, and you have to play it near-perfectly...but in the end, it is winnable. In my opinion it's probably 60:40 in Mario's favour.
JesusMorpheus Why should we consider taking him to T&C ?
GHNeko , do you think Cloud has any stage that he absolutely does not want to go against Mega?
