For shorts, look for The Last Question by Isaac Asimov, and any collections of Heinlein’s or Robert Sheckley’s short stories.
It’s beyond the OP, but I’ll suggest all the same The Caves of Steel and its sequel The Naked Sun by Isaac Asimov.
I agree with Chronos – pick up an anthology of Hugo winners for Best Novella and Best Short Story. There will be a strong overlap between our list and those anthologies.
A few others:
The Forever War - Joe Haldeman
The Foundation Trilogy - Isaac Asimov (the sequels are crap, but the originals are rightly classics.)
The Icerigger Trilogy - Alan Dean Foster
If your tastes run to military/sneak & peak/snoop & poop, then I cannot recommend the Sten series by Chris Bunch and Alan Cole highly enough.
Directly to the OP, I would suggest:
A Canticle For Leibowitz - Walter Miller
Lucifer’s Hammer and Oath of Fealty - Niven/Pournelle
The Long ARM of Gil Hamilton - Larry Niven
Lois McMaster Bujold - probably best to start with the Vorkosigan stories in chronological order. Falling Free is great - pre-Vorkosigan but great. Then Shards of Honor, then follow this list: Linky Her fantasies are good also, I particularly like The Curse of Chalion. Wonderfully drawn, and greatly wounded, characters, and the most natural alternate religions I have seen.
I’m a huge fan of Bruce Sterling. Islands in the Net is the best near-future extrapolation I’ve ever read - and I’ve read quite a few. Chrystal Express has some amazing stories, but a lot of their power is that they turn standard SF tropes on their heads. If you haven’t read a zillion stories like those, you may not appreciate what Sterling did there. OTOH, you must read “The Beautiful and the Sublime”. It is. The Difference Engine is not my favorite, but it has The. Best. Alternate. History. Premise. Ever.
Kim Stanley Robinson - start with Escape from Kathmandu, and move on to the California trilogy. Also the Mars Trilogy. Great stuff - and a lot of words for your trip.
For all of these authors I like their characterizations. That’s a weak point in a lot of SF. 
I’ll second the suggestion of grabbing some Dozios collections. Find authors there you like and read more by them. That’s better than following my suggestions.
I’ll have to disagree about Brin’s Earth - it’s my least favorite of his. Despite the incredibly cool techno gadgets. Gravity lasers - it does not get cooler than that! Brin needs an editor - stat! Maybe two editors. Try some of his early stuff and see how you like it. His Uplift series is set in a wonderfully rich and complex universe.
Brin’s The Postman is a very moving post-apocalyptic story. Best to pretend the Costner movie does not exist.
Harlan Ellison has some good stuff - some of it very outre. He writes well, despite all of the Ellison stories we shared at Gettysdope. Or maybe he writes well because he’s such a jerk in person. 
(He was quite civilized to me. Maybe it was an unusual day.)
I’ve read some H. G . Wells recently, and liked it. I’ve heard there are some good translations of Jules Verne out there now. Apparently the older translations stank on ice.
Niven and Pournelle’s The Mote in God’s Eye is a favorite of mine. The aliens are really, really alien they aren’t just Japanese in scales or fur. Well done, and a rollicking adventure.
Hal Clement is good also. I could do this all night, but I’ve got to sleep.
ETA: When you’re ready - Cordwainer Smith. Try a collection with “Scanners Live in Vain” - that’s what hooked me in. When he’s off, his stories are a bit slow. When he’s on - they positively crackle.
If you want some near-future SF that’s more technological, I’d recommend trying “Inherit the Stars” by James P. Hogan. The quality of his work may have dropped off in recent years, but this was a fun read. Sort of a scientific mystery story. I also enjoyed “The Genesis Machine” and “The Two Faces of Tomorrow” by the same author.
Other great Heinlein books:
The Door into Summer
Tunnel in the Sky
Citizen of the Galaxy
Starship Troopers
Many, many more. If you can find The Moon is a Harsh Mistress, start with that. If you can’t, any of the above books are a great intro to Heinlein.
His short story collections are great. If you can find any Heinlein short story collections, it’s hard to go wrong.
Interestingly enough, I had the opposite experience with the Mars trilogy. I tried reading them in high school, got through Red Mars by the skin of my teeth, and gave up partway through Blue Mars (or was it Green? The second one anyway). The writing just really, really disagreed with me – I remember finding it horrifically dull and long-winded scientific writing with the occasional teasing glimpse of character exploration or action that kept me plowing forward in the hopes of some nebulous payoff that never came.
Maybe we were reading mirror universe versions of the books? 
A postapocalyptic recommendation from other people that I’m sharing: I have S.M. Stirling’s Dies the Fire on my to-read list since it’s been ballyhooed by quite a few people here and elsewhere. I’ve enjoyed some of Stirling’s other military fiction, so I suspect I’ll also enjoy Dies the Fire. Might be worth looking into.
Assuming you’re okay with Military Sci-fi (Marines specifically) you may enjoy the Heritage Trilogy, Legacy Trilogy & Inheritance Trilogy.
They start with Semper Mars in 2040 (excerpt here) after the US has split from the UN and ruins have been found under the Martian desert (Cydonia to be exact), the rest of the first trilogy is set with a new generation of the families in Semper Mars up to I think it was 150 years out from the original story.
The Legacy Trilogy is set IIRC 500 years after that, and Inheritance 1,000 years.
The second two trilogies deal with the results of finding out humanity is not alone and the reason for the apparent Fermi Paradox.
Waaah?
Vernor Vinge The Peace War and Marooned in Realtime - basically takes one significant apocalypse-causing invention (I won’t say what it is, since it’s a plot point) and teases out a whole slew of consequences starting from the present day and moving onwards hundreds and thousands of years. Changes in society are a big theme. Not an alien in sight ;). Also, Vinge is a damn good character-driven storyteller.
I recently read his Eternity Road. Fits the OP well - set about 700 years after something happened to most of the people on Earth, who were quite technologically advanced at the time. Highly recommended.
Joe
I’m quite partial to Stephen R. Donaldson’s Gap Series, myself. Though some of the themes are unpalatable, to say the least, the story in itself more than makes up for it. Not for the weak of heart, but a great space opera nonetheless.
If you can find it, my favorite post-apocalypse novel is Hiero’s Journey by Sterling Lanier. It’s set long after a nuclear & biological war, long enough that civilization has started to recover from “The Death”. All manner of mutant creatures, telepaths, nasty bad guys ( human and otherwise ).
What? No William Gibson yet? His works might be liked or not, but you can’t deny that he was influential author. Especially Neuromancer is on every must-read SF list. It made cyberpunk what it is now and injected cyberspace-related culture into mass consciousness.
The Demolished Man by Alfred Bester is set in a future in which crime is almost nonexistent because of a telepathic police force. Great example of how science fiction was exploring psychological and sociological themes in the 1950s.
If you’ve never read Science Fiction, and you don’t know which authors you’d like, or which type of fiction, I’d strongly recommend an anthology. Arguably the best is The Science Fiction Hall of Fame which is still in print:
Volume I has the winners of a poll of the best short stories. Volumes IIA and IIB are the best novellas. I highly recommend all three.
(Volumes III and IV aren’t in print any more. That should tell you something. Ignore them.)
The only problem s that this came out in the 1970s, so it’s a bit dated. But good SF doesn’t go out of style. This is still essential reading.
I was going to suggest Asimov but I see that the Foundation and Robot novels have been mentioned. I wish I could read them (especially Foundation Trilogy) for the first time again…
Peter F Hamilton is an enjoyable read. The Greg Mandel Trilogy fits the OP well but I’d also recommend the Night’s Dawn Trilogy. Long books but don’t get put off, you’ll get sucked in!
How about:
Ringworld and The Ringworld Engineers by Larry Niven
Steel Beach by John Varley (or anything else by Varley)
Neuromancer by William Gibson (also Count Zero, Mona Lisa Overdrive)
Cryptonomicon by Neal Stephenson (also Snow Crash, Diamond Age, The Baroque Cycle)
More fantasy-like than pure SF, but how about American Gods by Neil Gaiman
Fun and a little thought-provoking, but especially fun the Stainless Steel Rat books by Harry Harrison.
Phillip Jose Farmer is a little on the pulpy side, but can be excellent. Check out the Riverworld books.
I’m not a huge Phillip K. Dick fan but he’s certainly part of the canon now and worth checking out.
Second the recommendation of SF short stories. I find that SF is especially well suited to the short story format. Dozois’s collections are good. Other good SF anthologists to look for in the used book stores: Donald Wollheim, Judith Merrill and the Dangerous Visions series edited by Harlan Ellison.
Yup.
Steel Beach is set on Luna, 200 years after near-omnipotent beings have destroyed all human life on Earth. It also deals with several technological innovations, including the perfection of body modification techniques. The Invaders aren’t dealt with in the book, so it’s not a shoot-em-up, Us vs. Them, book.
One of my favorite books.
Sten and Company spend part of the series as MANTIS operatives, MANTIS being the Emperor’s Intelligence service. They do whatever is necessary, be it spying, counter-intelligence, assassination, covert ops, you name it. They sneak in and peek at what the Bad Guys are doing. They snoop and then bring back the poop.