Boo, I just recently got the Hanzo legendary so now I'll seem like a bandwagon-er for wanting to use it.
Genji nerfs might seem overboard but they probably don't like the overall level of mobility/burst he has compared to other characters. It might be less about competitive balance per se and more about the baseline they want each character to be anchored around; Genji was probably just too far outside the harbor so to speak. Pharah trades off her aerial advantage with poor mobility, but Genji can spend most of his time airborne without a similar tradeoff. Also Blizzard normally doesn't like it when animation cancelling becomes the optimal way to play (they have a similar problem with Demon Hunters in WoW which they are trying to get rid of).
In terms of Lucio/Zenyatta, I don't expect any major changes in competitive. Discord is still superior to every other debuff in the game, let alone comparing it to Mercy. Mercy can only buff one character's damage and it means she has to forgo healing. Zenyatta can both heal and dps while using discord, and more importantly, it applies to enemy characters and not friendly characters which means you can get up to 6x the damage compared to Mercy. Their main problem is that abilities/mechanics like that are just so fundamentally good that nothing else will ever compare. An ability that makes an enemy take X% more damage from all sources is always going to be mechanically superior to an ability that buffs a friendly character's damage by X%, full stop. It doesn't matter what number you put in for X, the enemy debuff option will always be the better choice.
Similarly, Lucio's movement speed buff is always going to be mandatory in my opinion because movement speed is king in an FPS. To help illustrate this point, imagine if Lucio's movement speed aura was actually a debuff that slowed the enemy team's movement. I think we all implicitly understand why that would be an amazingly powerful and extremely frustrating ability to play against; but nothing is different just because Lucio buffs your team. It's all about the relative speed anyway, how Team A moves faster than Team B is less important than the fact that they do move faster. Overwatch is supposed to be a game where choke-points are important and more static defense characters are relevant. Lucio utterly negates that design and says, "nah, we're just gonna run past everything and blow up your healer immediately" (I would argue the extremely powerful and mobile offensive characters also hurt that design as well).
Furthermore, Lucio/Zen's ults are some of the best in the game because they prevent death and "pause" the action, thus they can serve as a counter to nearly every situation and they are offensively useful to boot. Mercy's revive is essentially a better version of Symmetra's teleporter, both of which are mechanically beneficial only if your team is dead so they cannot really be used offensively to take control points or push a payload. You can look at the MOBA scene for design analogy, but the idea is that self-revives and things of that nature don't normally change the outcome of a fight because the important part of the fight is over before they come into play.