"Wrong Side of the Tracks" for sure. It took me a few goes (then again, I sucked ass at SA when I first played it, hahaha), but I was a bit surprised when I went online and found out how infamous it is. I believe the secret to that mission (been ages since I played it) is that you have to keep about nother train's width away from the train, because if you're any closer, Smoke can't hit the Vagos. I will say that when I first failed the mission and heard the infamous line (c'mon, you know it), I was like "... what do you think I was doing, a**hole? Enjoying the scenery?" Hahaha.
I'll throw "Supply Lines..." in there too, although there's a very good reason for this one. When I first played it, I was shocked at just how little trouble it gave me (it also took me a couple tries, but I was hardly stuck on it), but then I found out that the mission was patched on later releases of the game, which are what I played. From what I've seen, yeah, the OG version is a nightmare.
I guess it's worth bringing up Vice City, too. I found a ton of missions in this really hard when I first played through it, but I was playing the Xbox version, and of course the aiming controls on the consoles are just plain f*cky by today's standards. When I copped the game on PC, I was shocked at how much easier the mouse aiming made things. It was still a challenge at times, but I never hit a brick wall.
... except "The Driver". F*ck that mission.