In addition to Tolkien, and some of the other excellent mentions above, I'd add:
City of Bones and Death of the Necromancer by Martha Wells.
Nightwatch by Sean Stewart. I didn't know there was a book of the same name by Pratchett. This book probably qualifies more as science fantasy, but it's definitely fantasy. And it's awesome.
Stardust by Neil Gaiman. A fairy tale for children aged 9 to 99 (or something like that, can't remember exactly what the dust jacket said). Great, great reimagining of classic fairy tales.
The books of the New Sun series by Gene Wolfe. Four books (or five, depending on how you look at the series. It's . . . complicated. Just like Wolfe's writing), including Shadow of the Torturer, Claw of the Conciliator, Sword of the Lictor, and Citadel of the Autarch. There are some other titles associated with the line of stories (it's a little confusing), but these are a good place to start. Wolfe is awesome. I've read the series several times, and I still can't tell you exactly what happens, because I'm not entirely sure myself, but the writing is amazing (Wolfe's vocabulary is astonishingly deep) and complex and nuanced and symbolic and . . . well, it's not everyone's cup of tea, but I think the man and his writing are genius.
The Sandman series of comics/graphic novels, by Neil Gaiman. One of my favorite quotes of all time comes from this series: "You got what everyone gets. You got a lifetime."
The original Conan (Robert Howard) stories are fun. Also excellent (I think, not everyone's cool with Leiber) are the Fahfrd/Grey Mouser stories from Fritz Leiber.
I like the Elric of Melnibone series from Moorcock, but his style isn't to everyone's taste either.
Warrior Poet