My vote is for World of Null-A by A. E. van Vogt (and not just because he was Canadian, either).
I read it when I was a callow youth, and it expanded my mind into thinking of things I had never thought of before.
{From this site.}
It depends a lot on who your aiming this at. There’s a lot of books which people argue, even on these boards, aren’t science fiction, because, you know, they aren’t like Star Trek.
A Canticle for Leibowitz, The Man in the High Castle, Slaughterhouse-Five, Flowers for Algernon, Fahrenheit 451, Replay, A Clockwork Orange.
That puts them in a slightly different place than Dune and The Left Hand of Darkness, two very fine novels under any circumstances but both set on other planets so that they look a little more like SF.
What about newer novels. You could try epics like Dan Simmon’s Hyperion or Ilium. Neal Stephenson has been writing novels that are sf in style and subject but not form, or is that form but not subject. Cryptonomicon and The Baroque Cycle read like mainstream but have the underlying sensibility of sf. Connie Willis I haven’t read lately, but everybody says that her Domesday Book is fat and full of character. Or something near-futurey like Distraction by Bruce Sterling.
Or we could go odd and talk about less famous writers like Geoff Ryman who have already slipped over into the mainstream in some ways, as with Was and The Child Garden. Or Lucius Shepherd and Life During Wartime. Sean Stewart with Mockingbird. Maureen McHugh and China Mountain Zhang. James Morrow, Towing Jehovah.
Or just forget the whole thing and hand over the latest Harry Potter.
Yes, but do you really want him representing the genre, when there are equally talented authors out there whose books don’t undermine the last 50 years of work toward gender quality?
Blasphemer! I’ll just pretend I didn’t read that.
Heinlein was, by far the most influential science fiction author. Not just in science fiction, but society at large. Heinlein was a vastly influential American, period. I believe he is one of a handful of people responsible for the growth of Libertarianism as a philosophy. He pushed an awful lot of kids towards science and engineering. During the Apollo era, Heinlein was a very popular figure amongst NASA types, and was a guest commentator for one of the networks for Apollo 11. Stranger in a Strange Land has been credited with having helped shape the '60’s era counterculture and ‘free love’ movement. He was also politically active, writing non-fiction and giving testimony to Congress. Starship Troopers was required reading at the Annapolis Naval Academy.
How many other authors in any field of literature have had that kind of influence?
Yes. He is that good.
How about “Childhood’s End” by Arthur C. Clarke.
Beautiful, elegant writing. Extraordinary vision. The novel seems to be about First Contact and LGM; but ends up showing us that we know as much about Life, The Universe, and Everything as a slug knows about the world beyond his puddle.
I’d have to say ** The Mote in God’s Eye ** as the quintessential science fiction novel.
It’s a roaring mix of Horatio Hornblower in space, entertaining characters, fantastic discoveries, heroism, deception, and a really good first contact story all in one book.
Beyond that, Gateway, Dune, and ** Neuromancer ** are my next choices. Even though Neuromancer is a cyberpunk novel, it’s got all the right parts- good characters, science fictional setting to bring out conflicts, good story, good writing, etc…
Seconded. Well, thirded, actually, since K364 has also proposed it.
I must admit, I’ve read very little Heinlein, and that little was a long time ago. Still, Childhood’s End was one of those books that sort of tinted the world for a while after I’d finished it, and it’s a rare book that does so for me.
The Moon is a Harsh Mistress
Fahrenheit 451
Childhood’s End
Canticle for Liebowitz
Forever War
Gateway
Foundation
Nightfall and Other Stories
The Illustrated Man
I second that nomination and add The Dispossed, her other great novel.
Heinlein’s best novel is The Moon is a Harsh Mistress.
Taking the thread title into a different direction, I’d like to nominate Fallen Angels by Niven, Pournelle, and Barnes as the quintessential book about science fiction.
OK, but the moment I get home we gotta bang like bunnies, regardless of whether either of us is in the mood or not, because Heinlein women are like that, and so are practically all men real or fictional! 
You’re definitely reading the wrong Heinlein books.
I should know. The Cat Who Walked Through Walls is the only book I have ever read halfway through and then quit.
Then I read The Moon is a Harsh Mistress, Double Star, Have Spacesuit, Will Travel, and a few others. And they were fantastic.
Still, in the end I agree with you on the Foundation series. Asimov is the master.
Also, the Elijah Baley novels should be mentioned. They’re right up at the top of the list too.
It’s this sentence that makes me recommend, hands down, Dune.
If you think about it, Dune isn’t really a sci fi novel at all. It’s a medieval drama that just happens to be set thousands of years from now. My sister can’t (or rather couldn’t) stand sci fi, yet I bought her the book for her birthday and convinced her to read it.
She loved it.
The interplay between Houses Atreidedes, Harkonen, and Corrino, the Bene Gessuret, the Spacing Guild… Even if you take the sci fi elements out of it, it’s still one Hell of an epic*. If you want to introduce somebody to Sci Fi, tell them to read Dune, and let them develop a small immunity to space travel and future technology. After that, you can start telling them about alternate views of the world, such as Ursala K. Le Guin. Or, possibly, far history like the Foundation series.
Just remember, if they were technophiles the would already be into sci fi. Start with Dune, see what they like about it, and go from there.
*But don’t let them read the sequels to Dune. That my kill any ember of interest they had. And if you see a copy of God Emperor of Dune in their place, steal it and tell them dingoes ate it.
Considering that I grew up in a time where everyone was afraid of the bomb (I remember having nightmares as a kid, that looked just like the dream Sarah Conner has in Terminator 2), this is my personal pick for the quintessential Science Fiction novel (at least for my generation). Don’t go telling me it’s not SF, because it is!
Also, who can resist the humour of a shopping list being a sacred relic. “Pound pastrami, can kraut, six bagels–bring home for Emma.” indeed.
WOOOOO HOOOOOOO!
Errrr…I meant…not tonight, honey, I gotta headache. 
Ingathering: The Complete People Stories of Zenna Henderson is well worth mentioning, as it touches your heart whilst feeding your head.
Buy it, dammit!
For me it would be Dune. But a close second would Zelazny’s Lord Of Light.
Stand on Zanzibar by John Brunner. A close second would be the aforementioned Doomsday Book.