I disagree with you OP. Mario is fine right now. He's a strong character, but he's not overpowered in the slightest. He has clear strengths and weaknesses right now. If we look at how results have been going for him (
https://smashboards.com/threads/tournament-placing-database-scoring-project.437773/) he is clearly a good character but nowhere near dominant.
Up tilt base knockback: 28 -> 42
Up tilt KBG: 130 -> 125
Down throw angle: 68 -> 65
Down throw KBG: 90 -> 96
These nerfs are hurting Mario's combo and damage racking game. Why is this necessary? Mario already tends to lose neutral harder than most of the cast by either range, raw damage per hit, mobility, lack of a real forwards approach move, or disjoints. He should be destroying characters when he gets in because he has limited means of doing so, and even then the only characters he destroys are fast-fallers and characters without a combo break option. The utilt change would only really affect his combo game on fast fallers anyway, as there tends to be better options for other weight and fall speed classes. On the flip side, those characters he destroys with combos tend to have a huge leg up on Mario in neutral.
If you really want to hurt his damage output, taking 1% off of Uair and maybe .5% off of Bair while compensating the KB for both would be a better "fix". I wouldn't agree with either of those changes, but they wouldn't destroy mario. Well, they probably would but w/e.
Up Smash base damage: 14 -> 13.8
Up smash KBG: 94 -> 92
Mario's Usmash doesn't need nerfs. It's only spammable against bad players, as most of the cast can dash grab Mario for free for Usmashing their shield (tethers just grab him straight up), and it's not hard to whiff punish otherwise. Don't get me wrong, it's a strong move. Strong moves are fine though. Characters need strong, defining moves or they'll lose their identity.
Fair startup: 15 frames -> 17 frames
Fair FAF: 60 -> 65
Fair autocancel: 43 -> 48
I'm legit lost on this one. Mario's fair is fine, there's a reason you don't see it used that much in top level outside of hard reads. Mario clearly pulls his fist back before swinging, so i'm not getting where this "discrete" startup is coming from. It has enough lag as is. Most of the cast can Usmash him out of shield for it, and a good bit can drop shield -> Dsmash him for it, or at least get a tilt in.
Super Jump Punch (finisher) KBG: 145 -> 130
SJP is fine as is too. It doesn't kill well unless you hit someone really close to the blastzone. Mario can combo you up there, yes, but as an early beefy smash doods video pointed out, a combo into this should never KO you unless you screw up and get grabbed on a platform. Mario already can't KO that well outside of raw smash reads, please don't nerf his KO potential.
F.L.U.D.D charge time: 98 frames -> 115 frames
That's nearly 2 seconds to charge a projectile that does no damage. Mario players already have to think about charging FLUDD, because you lose options when you do so. Since you can't B reverse it and can only shield cancel FLUDD, the opponent can narrow down mario's options depending on whether he charges facing away or towards you.
Away: he can threaten you quickly with Bair, Usmash, Nair, or SJP, all of which sans Usmash require Mario to jump and leave the ground. That's commitment, and all of these options lose to run up shield. Since Mario can only shield cancel FLUDD, he can't quickly threaten you from the ground with strikes or movement.
Towards: He can grab, Nair, SJP or shoot you with FLUDD. Grab loses to spacing and shooting FLUDD in neutral usually doesn't accomplish much unless the opponent is jumping recklessly, and obviously puts him back at square 1 for charging the move. I've covered to other two options' commitments above.
As for how effective it is against predictable recoveries, that's the point of the move. It needs to be good at that. I don't think you're giving enough credit to what Mario gives up in order to charge, so you're nerfing this move without sufficient reason.