Without directly challenging or risking hitting Mario's invincible head, Dtilt which for many, is the universal sweep option? In Sonic's case, he can probably Ftilt as well. Mario's hitboxes haven't been posted, but assuming it doesn't start on the ground, then regardless if it's his front or back hit, his legs are definitely going to be vulnerable. Body is too, but it would be safer to go for the legs since it probably starts at least waist high. So, assuming it's kind of like Brawl's Up Smash:
http://smashboards.com/threads/the-hidden-block-marios-hitbox-repository.288507/. If Mario's Side Smash is that disjointed, he could sweet-spot a Side Smash against another Mario. Probably would have to angle it down. There's also the disjointed and invincible Super Jump Punch.
For Sheik, Needle Storm's probably the only other option. Speaking of which, assuming Mario's charging it a lot and leaving him stationary, Mario, Sheik, and ZSS can all use their projectiles to punish. Probably will need to run a way which won't be a problem for the 2 queens. Mario won't be getting much outside of damage, but it's his damage he's inflicting even if it's little. The other Mario would have to release if he wants to avoid damage by clanking with the projectile. With FLUDD, he just gets pushed back, so stage control. For ZSS, if it connects, that's a free stun that she can capitalize on, especially if the other Mario decided to be stupid and duel with ZSS. Lose that, don't hit the projectile, and there you go, full stun. Back to Sheik, aerial Needles can probably clip his legs which could lead to a Bouncing Fish. I say could because charging Smashes leads to more knockback. Landing Dair, if disjointed enough, could work too.
For Sonic, Ftilt and Dtilt were covered. Like Mario, he could Side Smash, but since it's probably not disjointed, would be riskier than Mario's. Spin Dash could work since it's invincible.
For ZSS, Paralyzer was covered, both her grab, Zair, and Plasma Whip can work. Nair could work too, but it would be risky and difficult to make sure you hit Mario's body and legs. Utilt could work too since it has horizontal range, has leg invincibility, and is recoilless like Ike's dash attack and Little Mac's Utilt so she could "eat" Mario's Up Smash with the first hit and hit with her second hit. Also, Down Smash and like Sheik, landing Dair if disjointed enough. I have no idea if a "short" Flip Jump could work to bait Mario to release Up Smash while she's invincible and then she hits him with the kick.
Outside of that, pretty much anything if you decide to challenge head which for some characters is really terrible while for others, doesn't matter like Marth challenging Mario's Up Smash head on with Side Smash won't be risking much since it's a natural disjoint, but Mewtwo deciding to run up and Fair is likely going to risk his Pokéskin.
Yoshi's Up Smash has 21 recovery frames. It's only 2 frames slower, has 1 less active frame for its clean hit and invincibility to Mario's entire Up Smash, and slightly shallower angle at 75 degrees to Mario's more vertical 83. Otherwise, it has similar knockback and same damage with its clean hit, but packs a 12% late hit for the other half. Over Mario, it has much higher vertical reach and covers horizontally just as well -- Yoshi's Up Smash covers maybe the entire lower platform of Battlefield --, and he can setup not confirm it, from jab and by falling down with Bair in a way like Fox can with Fair. There's more -- you just need to take time to look at frame data -- and like I said, Dr. Mario and Luigi's Up Smashes could be argued as better than Mario's.
For Mario's Side Smash, it does have a weaknesses in that it doesn't have the range or coverage of other Smashes. For example, it doesn't have Diddy's horizontal range and it doesn't have Marth's arcing hit. It also doesn't really have reliable setups. He can set it up with frame traps?, locks, and reading poor decisions like choosing to air dodge down from Mario hitting you with Dtilt, but he can't outright confirm it like Diddy, Marth, and Toon Link? can.
Also, it's not really that fast. As a Side Smash, it's kind of average at frame 15. As a move, it would be on the below-average side. From a glance, Diddy, Fox, Greninja, Kirby, Little Mac, Lucina, Luigi, Marth, Olimar, the Pits, Roy -- barely --, Samus, and ZSS all have faster Side Smashes. Regarding its recovery, it's also average at 31 frames. All of that, its average startup and recovery, short range, and linear hitbox get made up by its sweet-spot being strong. Also, technically Dr. Mario's Side Smash is a bit better, even when sour-spotted.