TWhy is Mario fun, because it's hard? No, because it's fun. Fun and difficulty aren't mutually exclusive. Never limit a fun (main) game mechanic unless you're going to replace it with another fun game mechanic. If you want to make it hard, then on the last level, have the protagonist turn the antagonist into a human, or other killable form, maybe trap him in whatever last possession he took, and limit them that way and give them another way, that's not frustrating, to beat the game... even though that's so cliche
Whatever you do, just don't make the game get progressively harder for no reason at all. Plenty of games barely progress in difficulty, but stay fun throughout. If it's too hard, people might start throwing their controllers like the old days 
SMB, nsmb, even mario kart double dash, these all get harder progressively because the player gets more experience. A game must have progressive difficulty because it can get boring. Even an easy game like Klonoa (PS1) got some hard parts, still the concept is crazily simple.
Also, what's bad about throwing controllers like the old days? Wasn't the game supposed to give nostalgia?