As a Fizz player and someone who's thought a lot about this, I feel that although Fizz is one of the stronger champions in the game, he is not overpowered. At the highest levels of the game, he is merely good, not dominant. However, I think that there are several factors that make Fizz much stronger at lower levels than he is at the highest levels, all of which boil down to the fact that playing against Fizz is in general more strategically demanding than playing as Fizz. A quick rundown of a few of Fizz's strengths and weaknesses are in order. First, the strengths:
- Strong all-in potential after level 3 (when he has all his abilities) and especially after 6 (when he gets his ult).
- E dodges/negates a huge variety of impactful abilities.
- Strong early power spikes with Sheen/Lich Bane.
- Two forms of engage/disengage make frequent trading possible (E and Q).
- Passive mitigates auto-attack harass.
- Tends to snowball if he picks up early kills.
And the weaknesses:
- Melee, so is vulnerable to ranged harass. This leads to very weak laning pre-level 3, and still somewhat weak pre-6, since his burst isn't yet high enough to force the opponent to back off completely.
- Abilities have fairly high mana costs and long cooldowns as compared to most champs. This means that he can't afford to spam his abilities in lane if he's not getting damage onto his opponent, and that he has windows of vulnerability after using his abilities (especially the E). In teamfights, this can make him a bit of a one-hit wonder (giant burst, but then tends to either retreat or just get in some incidental damage before dying; this means he can be low-impact if he can't insta-gib a carry).
I won't attempt to address teamfighting against Fizz, but a few words about laning are in order (since this is where the snowball begins). I'll use the Syndra vs. Fizz matchup as an example. As Syndra, you need to harass Fizz heavily pre-6 (even more so pre-3) using your auto-attack and Q (Dark Sphere). This ability is a great tool for harassing Fizz because its low cost/cooldown means you can spam it, and Fizz simply can't troll-pole away from every one. To line up the Q, it is important to pay attention to the health of your minions and predict where Fizz will move in order to last-hit. In this way, you can build up a large CS lead or force Fizz out of lane early. In particular, it is important not to burn your other abilities until Fizz burns his E, as these abilities are much more impactful and costly , and Fizz is likely to win a trade if he dodges one. Meanwhile, as Fizz, you're looking to dodge Syndra's abilities if possible and either just survive early laning with roughly equal CS, or burst Syndra if you can dodge a more impactful ability with your E, or if she doesn't respect your burst and gets too low.
At the highest levels, Syndra vs. Fizz is generally regarded as a skill matchup, if a somewhat volatile one. At lower levels, however, I think Fizz holds the edge because the things the matchup demands of Syndra (paying attention to her own minions' health, predicting enemy movements, keeping track of opponent's cooldowns) are more advanced than what it demands of Fizz (CSing his own minions and looking for opportunities to dodge abilities or get aggressive). Also, I think players at lower levels tend to underestimate Fizz's burst or play too aggressively/impatiently.
Probably the best thing you can do to help you play better against Fizz is to play a few games as Fizz. If your opponents are good enough, you should eventually see how constricting his mana costs/cooldowns can be, and how much you can get harassed at low levels. (If you want to feel it right away, grab a friend and try to lane as Fizz against Akali. It hurts.)
All that being said...I might not mind it if they nerfed Fizz's Passive (Nimble Fighter) by making it not reduce damage from auto-attacks. Fizz's weakness to early ranged harass is a key weakness, and it might be ok if they widened the window to harass Fizz. Also, I don't understand how being nimble makes you take less damage when you've already been smacked in the face.