Coming from Warcraft 3, there were two things that stuck out in my mind. One was in Ashenvale, when I traveled there as an orc and found the scattered remnants of the Burning Legion in the Demonfall Canyon. Heading in there and finding the sight where Mannoroth was destroyed was really cool.
The other was the Plaguelands (both of them). The Cult of the Damned, Uther’s Tomb, Stratholme, wandering through all those memories and battling against the entrenched forces there was a lot of fun.