Old school deadmines. Mr.smite is a personal favorite of mine!
I loved SFK for its atmosphere and length - not too long, not too short. There was also that slight thrill of trespassing Horde territory. At level 60 I loved UBRS and Scholo, Strat was amazing as well. I have probably ran UBRS over 20 times to get Magister's Regalia.. ;)
It's gotta be Scarlet Monastery for me. I think I practically lived in that cathedral one summer during my quest from 30-40 as a Paladin. It seemed like it took the entire summer to finally make it to 40 for my mount, and each level up got me just one step closer and closer... But also because I was apart of so many PuGs for those dungeons, I met a lot of friends along the way, joined guilds, etc. I think that's the most memorable part for me is just the social aspect.
The rewards were great too -- especially as a retribution Paladin! The drops from the Armory wing were very nice.
My favorite dungeons are Shadowfang keep, Zul'Farrak, Sunken Temple - yea i really like this dungeon, there are cool weapon and armor drops, and first time you meet dragons in dungeon, and Scarlet Monastery. But in fact i love all dungeon content in vanilla and that's why i'm here :)
I think Scarlet Monastery is cool, as well as Stratholme. I don't think I ever ran Scholomance in-era, but I like it thematically. In general I guess I tend to prefer the Upper-Eastern Kingdoms Scourge-flavored dungeons.
I also remember liking UBRS back in the day, just because it was fun to do a 3-group Mini Raid. I think I did it during the 3-group era, anyway. Really foggy memories, but the idea that I was doing a raid-style dungeon was like, "Alright, this is an endgame dungeon now, real shit." Ended up running it a lot to get my Valor shoulders (Causing the other warrior in the group to lose his mind).
And a special mention for RFC. The dungeon itself is kind of whatever, verging on modern-WoW dungeon design in its simplicity, but I always look forward to doing it because it's the first time you get to try out how your new character plays in a group.
The fact that you're cleansing the land off undead filth, helping the Argent Dawn, you even wear a trinket so that filthy scourge knows who is coming. All the background lore from WC3, the interesting bosses like the mysterious Unforgiven, young Timmy or one of the four horsemen itself, Baron Rivendare. The loot is also really good, it even comes with an extra challenge for 'speed-running' it...
Stratholme is by far the best dungeon in WoW Classic (my personal opinion).