Some of these will be repeats, but that just makes them extra-recommended!
Sci-Fi:
Anything by
Ursula K. LeGuin. I'd particularly recommend "The Dispossessed."
She's got the most thought-provoking work I've ever read that didn't come across as preachy.
Orson Scott Card's "Ender's Game" is a must-read. I haven't read the rest of that sequence, but I really didn't like the one other book of his I read. "Homecoming: Earth" or somesuch.
Stephen R. Donaldson's "Into the Gap" series. I'd strongly recommend anything he wrote, but I know a lot of people don't care for his stuff.
C.J. Cherryh's Morgaine cycle. Just skip the last one; I wish I did.
Walter M. Miller "A Canticle for Leibowitz." The title intrigued me in the airport used-book store. I was blown away.
Margaret Atwood's "The Handmaid's Tale" Is very frightening how much of this came to pass.
Phillip Jose Farmer's Riverworld series. Much better than the Sci-Fi network movie...
Not sure if this fits but "Smila's Sense of Snow" by
Peter Hoeg. Quite a bit better than the movie.
Fantasy:
I think
Robert Aspirin's Myth series has been mentioned. Of course, you have to be able to deal with puns, but if you've made it past the titles ("Little Myth Marker", "Myth Inc. Link", etc.) then you're probably fine
Roger Zelazny's "The Chronicles of Amber." The more of his stuff I read, the more impressed I am.
Guy Gavriel Kay's "The Fionavar Tapestry." Took me a little while to get going, but then I was hooked.
I'm sure there's much more, but sleep calls
