The Stars My Destination by Alfred Bester. Lickety-split, full-throttle space opera with a marvellous anti-hero.
Snow Crash by Neal Stephenson. Cyberpunk in a libertarian dystopia. Stephenson can really write, and can hold his own with any acclaimed modern “mainstream” writer, IMO. He’s very funny and full of ideas. The only thing people have problems with is that he’s not a great plotter, and his books spread off into tangents and then just stop, rather than end. But if you can get used to that and read for the tangents rather than the story, he’s very entertaining. I’d start with this before the denser Cryptonomicon. Snow Crash is worth it for the toilet-paper pool memo alone.
Iain M. Banks. I recommend a start with Player of Games
Rather than suggest a specific book, since you stated that you’re new to science fiction, can I give you a piece of advice? Don’t get overly wrapped around the details of the technology. I don’t see any real “Hard” science fiction listed so far, so it really doesn’t matter. When they talk about the super-hyper-flux-drive as being engaged, just know that they mean something to take them from point a to b really fast. Same with aliens. Don’t get too bogged down in the details. “Ok, some sort of lizard thing that likes to fight” is about all I worry about when I read some of these descriptions that unless they came with an illustration I wouldn’t be able to figure out. If you spend a lot of time trying to figure out how something works you’ll just get frustrated and bogged down.
I’ll ditto the **Mars Trilogy **by Kim Stanley Robinson. Especially Red Mars, which is the best one. I found them all to be quite fascinating. It’s got space travel, but no aliens-- it’s actually more about how we construct societies, how we could start anew on Mars. . . or bring the worst of Earth along with us.
That said, they’re not easy reads, and some of the elements are off-putting (I can see why the earlier poster didn’t like them-- I barely liked them. . . yet I’m recommending them here, how weird ;-).
Basically, KSR isn’t much for characterization, and his politics/economics are kooky-wacko, but the sheer sweep of his novels can be breathtaking. Once I was done with Red Mars, I actually felt angry that I’m not going to live in a world where we’ve colonized the planet. It just feels like we’re missing out, like with that whole “flying cars” scam we keep being promised.
Oh, and ditto The Sparrow. I know, space travel & aliens, two things you didn’t want, but it’s a very unique book.
Can’t go wrong with some Ursula Leguin - my favourite of hers is The Dispossessed.
Also I recommend The Child Garden by Geoff Ryman, post-apocalyptic with a twist!
The Carpet Makers by Andreas Eschbach
Quite similar to Iain M Banks (which is a good thing IMO). Actually I beleive this book was suggested to me by someone on this board, when I posted a similar thread to yours a while ago.
I know I’m very late to the party but I’ll toss my two cents in and stir up a hornet’s nest. There is a very large portion of science fiction and fantasy fandom that is satisfied just with the concepts in the novel and overlook massive problems with the rest of the book if the idea is cool enough. Consequently there are quite a few SF books that are very popular despite being completely terrible. My point is this: whatever you wind up getting don’t judge the whole on it. SF is a big umbrella and there’s definitely something under it you would like even if you don’t care for what many SF fans recommend.
For Neil Stephenson my preference is The Diamond Age. It does have the same problem that his other books do where he suddenly realizes he has four pages left and hasn’t resolved his plot so he crams it in. However, the rest of the book is a fairly clever story of a girl from the poorest of families rising through society simply be having the right book come into her hands. I think it’s a bit more refined in style than Snow Crash (which is very good) and doesn’t get completely lost in digressions like Cryptonomicon (which I suspect might be very good if an editor attacked it with a chainsaw and cut out two-thirds to half of the 900 pages).
I recently read Nicola Griffith’s Slow River and found it to be spectacular. It’s a three tiered story of a woman growing up a wealthy but broken home, the abusive relationship she winds up in after leaving them, and how she tries to put a life together leaving both behind. Griffith weaves the three stories together wonderfully using a theme of sewage processing.
I enjoy Bujold’s science fiction quite a bit and dislike her fantasy efforts. She doesn’t tell a deep story but they are compelling adventures. However reading in “chronological order” is the wrong way to go about things (Bujold jumped around a bit in her history). Most of her early work isn’t that great and Falling Free is one of her worst. Shards of Honor is her first published work and it shows. To pick one point on the dart board to start with I’d say begin with Borders of Infinity. It’s actually three linked novellas using the same main character that Bujold features in most of her science fiction books. It will give you a good taste for the flavor of the series.
If it’s the series that I’m thinking of volumes three and four are the first ten years worth of Nebula award winners so there is quite a bit of good stuff in them though in fairness everything there has been reprinted in other anthologies.
I see we both have good taste.
One of my favorites, A Fall of Moondust Arthur C Clarke.
To emphasize the point – most awesome science fiction is about the storytelling. If you get tripped up twice a paragraph on the fictional science, you can’t enjoy the fiction too well.
Given that, the list of Hugo winners includes “Neutron Star” by Larry Niven, an excellent short story of hard SF. He took an idea voiced by Isaac Asimov (in a nutshell, describing a neutron star while making the story entertaining) and mixed it with his own setting (a ship impervious to all emissions except visible light comes back with its crew dead, and the protagonist has to find out what happened). The hard science discussion comes at the end of the story, in the resolution to What Killed the Last Crew.
For H. Beam Piper fans I recommend Project Gutenberg. Distributed Proofreaders have put a lot of his stuff on line this past year.
The fuzzy story mentioned above.
I 99th the early Heinlein books, the Scalzi books and the Morgan books. I would hold off on “A Canticle for Liebowitz.” I’ve been reading sci-fi for decades, have read this one three times trying to find the love, and stlll think it blows big chunks.
Grr and I forgot to mention the Vorkosigan books by Lois McMaster Bujold. I Lurrrrvvv me some Miles, not to mention Cordelia and Aral.
Since the OP asks about post-apocalypse books, I’m a bit astonished at being the first to mention Earth Abides by George R. Stewart. You might also consider Nevil Shute’s On the Beach: a good novel even if it is by a “mainstream” writer, and even if it is, strictly speaking, not post-apocalyptic but waiting for the apocalypse.
Extra votes for the Heinlein and Scalzi picks, and for The Demolished Man and Little Fuzzy, which is on Gutenberg.
Short fiction: An Arthur C. Clarke anthology. Clarke’s shorts are mindblowing. Don’t miss “The Nine Billion Names of God”, and on the lighter side, any of the “White Hart” stories.
Get a Larry Niven collection too–“Inconstant Moon”, “Man of Steel, Woman of Kleenex”, those “Hole in Space” stories where he outlines practical problems with teleportation, and then explores the problems it would cause if it DID work (like unsolvable murders and instant riots).
You might like Sheri S. Tepper. I think The Gate to Woman’s Country fits most of your criteria. Near future, no aliens, post apocalyptic - check check check.
If we’re going to talk about Earth Abides, I’ll toss in Alas, Babylon by Pat Frank. Both are classic postapocalyptic books, I think. However, they do both have their share of warts. There’ve been discussions about Earth Abides before, more specifically about gender roles and the protagonist, but I can’t remember specifically about the latter book.
I’ll chime in with Gateway, by Frederik Pohl. From the wiki entry:
Ok, so I leave for my trip tomorrow, and there were so many good suggestions it was hard to make a choice, but here’s what I got:
The Moon is a Harsh Mistress, Robert Heinlein
A Canticle for Leibowitz, Walter Miller
Now which one will I start first??! 
Probably The Moon is a Harsh Mistress since it seems to have gotten the most overwhelming response here.
Of course, keep the suggestions coming, because I will be relying on this thread again to inform my future book choices.
p.s. Earth Abides also made my short list, but the bookstore was out of it at the moment…
Beware! On The Beach is a tremendous downer. I’d start with TMIAHM, then ACFL. Make your first two SF books absolute classics.
Dying Inside by Robert Silverberg
Way Station by Clifford Simak
To Your Scattered Bodies Go by Philip Jose Farmer (DON’T read the sequels)
Damnation Alley by Roger Zelazny, who also wrote Lord of Light
Almost anything by CJ Cherryh
Cities in Flight by James Blish
If you are reading many of the books listed in this thread for the first time, I truly envy you. I swear I’ve learned more about human nature and society from sci-fi than any other source, and sometimes the concepts developed by these authors could literally make me gasp in awe.
Oh yes, tremendous book, and at least one very good sequel Beyond the Blue Event Horizon.