Speaking of fox over Mario, he has some solid kill confirms off of landing dair, running ftilt (backside hitbox), and I believe at certain percent u-tilt or dash attack lead to uair kills.
His PP is huge, his foxtrot is above average... So I see his movement getting better as time goes on. His combo game is being optimized in training mode but still has room to grow at a high level. I can see the character improving in this way, with a bayonetta like (not as good obv) touch of death type feel where he opens with anything and can convert with that hard. For instance, a rising dair actually autocancels on Battlefield platforms, which can combo into uair. Unfortunately character specific combos will continue to grow specifically on him, as he is uniquely susceptible. So... i guess all im getting at is, better than mario!
I think bayo hurts him specifically because of his style, he is very vulnerable to bat within and witch time, as well as high level edgeguarding. Actually, edgeguarding will also continue to grow against him. The more i think about him, the more I see him falling.
If we count shiek out, he is often a Worst MU for characters. If they lack ways to escape his utilt strings they are devastating. Same if they can't land. Autocanceled u-air into utilt is as close as he has to braindead confirms, since many characters cant land unless they make a risky maneuver. I could see him doing well against MK. High aggression and very mobile neutral, good at juggling. Sure MK edgeguards him well, but its not like he is particularly good at getting fox offstage and offstage fox should be dead anyways. But this isn't even always true in melee, I think players underestimate the resilience of a skilled offstage player. (come in low, tech jump the stage spike, and you're back!)
EDIT: Top level play has Mario as one of the best choices against Shiek. This alone is a huge boon. ZSS outkills him, but Mario benefits from Battlefield layouts so at least he has that making her choices harder and opening ladder kills for him if she picks these stages, otherwise he gets some survivability ESPECIALLY with weaker Boost Kick... Rosa is a trouble MU though. Much like fox, he is a problem MU for many characters... again for utilt train stuff, as well as a reflector and great gimping tools. How does FLUDD play out against Bayonetta? I could see it working well, with a gimping tool that actually can't be Bat within or Witch Time'd.
Huge grab reward is another thing that solidifies his position in my mind, with mobility and flexible usage aerials also helping his case.
There was some bustlings about him getting a kill confirm with landing dair, I think landing dair > PP > JC Usmash was a true combo at kill percents in training mode? I'm not sure what came of that.