Sej was only "too strong" before the 500 nerfs (exaggeration) that were given to both her AND Cinderhulk in the same patches.
Lee Sin has received love taps in the past, but they've barely changed him at all. Of course, it's expected for the generalist to not be as good at other roles champions can do, but he just has SO MUCH in his power budget that it seriously makes you wonder why it's been like this for SO LONG.
When a generalist like Lee comes along, he is supposed to have the same power budget as other champions, but it be divided into smaller categories (I.e. he can have the traits you described other champions who are (supposed to be) doing his job better). When Lee has this much stuff, all of it has to be relatively weak to keep his power budget equalized with others.
This hasn't really been the case. Just to give you an idea, at level 18, he is capable of doing 340 + (180% Bonus AD) + (8% missing health) in physical damage just from Q and follow-up, then his E does 200 + (+100% bonus AD) and also a 60% slow on follow-up. Finally, he can ult for 600 + (200% bonus AD), which also gives one of the most powerful knockbacks in the game. That's 1140 + (480% bonus AD) + (8% missing health) in the span of about 1.5 seconds. This is also not counting the fact he has 2 gapclosers and 350 base movespeed, which can keep up with or outrun every champion except Gnar (mini, at level 18), Elise (spider), Master Yi, and Pantheon. And most players build him tanky, not to mention.
I'm not saying that he's the worst champion ever made, but something HAS to go. Like, seriously, I'm not sure how this kit is allowed to function the way it is