You guys are giving way too much importance to genji waiting for his i can kill the whole team moment. Of course he can wreck your entire team. So can li ming and gmane with two low health targets. You can complain about how genji has an easier time executing than li ming, sure, that's valid if u want to focus on that. It really isn't the issue at hand how well killers can kill things. Seriously just consider all the ways stukov makes his life miserable.
Burst heal means he can be baited onto a low target
Aoe burst and dot in general limiting his opportunities
If he gets autoed once he gets like a 5th of his health chunked
If you tag him with w on his way out of harass your team can catch up to him easy
8 sec cd aoe silence (a lil more on this: e means he has to walk out, you can absolutely add that time to his real cc count, in practice his e is a mini-horrify to most and ppl who sit on it usually regret it. lingering e is really strong but you don't need it for genji because you can just channel that shit, the 13 just lets you do it when you're not in a good channel spot.)
Both ults counter his ult
Literally the only way for genji to have a happy engage is for his team to do all the work and him coming in to ks, that's a 4v5.
Genji's pros against stukov: can dive him and chase him down if he's alone or not near something
If you want to say the silence is hard to use, fine. But think about it this way. Malthael ults in and gets silenced. He cant q for heal/dmg which he relies on heavily whenever he goes in, like most ppl he has to pretend it's horrify because walking through it takes too long, his dot does pretty shitty damage with no q, the marks run out on good escape targets, hooray happy counter right? And it's really not much to ask for a stukov to put his e on an ulting malthael, you know what he who to get on, you know who he can w to, i really reject the idea that this is a difficult thing to do. You can pretty much substitute genji in for all of this. Genji relies like a motherfucker on using his skills correctly and stukov stops everything cold. All that's necessary here is to identify genji's moment and play accordingly. Like it's a good idea to stand next to uther when you're a squishy agaibst genji right? Stukov got u from downtown, dont worry about where you are standing as much.
This on top of being a support, meaning the rest of your comp can pick even more shit that makes him miserable. Before youd have, what, malf ult and root zone, tass shield, uther everything, bw w. Stukov fuks with genji in a major way with every single tool he has.