Zelazny? Duh. I meant Samuel R. Delaney. :smack:
John Varley:
Steel Beach
Millenium
Gaea Trilogy: Titan, Wizard, Demon
Robert Charles Wilson:
The Bridge of Years
The Harvest
Dan Simmons:
Hyperion
Fall of Hyperion
Endymion
Rise of Endymion
My SO and I have been enjoying his latest work: a companion series told from the viewpoint of Bean. Not so much SF as it is a book-long mindgame, it reads like a good spy novel, if there is such a thing. Anyway, Bean makes Ender look like a bumbling moron. I’d recommend it to the OP, as he says he likes alternate histories, and this kind of bridges the gap between that and sci-fi.
Any of the “Culture” novels by Iain M Banks make very good reading.
The Dispossessed or The Left Hand of Darkness by Ursula K Le Guin are a couple of classic stories.
Nearly anything by Philip K Dick, perhaps The Man in the High Castle would be a good choice.
V
Armor by John Steakley
Voice of the Whirlwind
Hardwired
and Days of Atonement all by Walter Jon Williams
Footfall by Larry Niven and Jerry Pournelle
The Island in the Sea of Time trilogy by SM Stirling
Footfall is a great suggestion. Lucifer’s Hammer, by the same authors, is also good.
The Integral Trees and The Smoke Ring by Niven. A totally fascinating setting (like Ringworld) for a great adventure.
Almost anything James P. Hogan wrote in the 80’s and 90’s is pretty accessible, considering that it is totally what is known as ‘hard SF.’ Try the Giants Trilogy (Inherit the Stars, The Gentle Giants of Ganemede, and Giants Star. He wrote another in that setting, Entoverse, but I don’t consider it part of the same story) or Bug Park. But whatever you do, don’t read Cradle of Saturn. It’s still a good adventure, but it gives credance to Veilikovsky. In the last half-decade or so, Hogan lost his formerly-scientific mind.
Oh, and by the way, you probably don’t want to read Baxter’s other Manifold books. I think Manifold: Time was the easiest of the set. Manifold: Origin will reallly torque your noodle.
Get a copy of ‘The Year’s Best Science Fiction,’ edited by Gardner Dozois. You should be able to pick up copies from the previous couple of years for very little in some bookshops and online. It contains about 30 stories that truly are among the best in the genre.
I’d also recommend Anne McCaffrey’s ‘The Ship Who Sang.’
I suggest one of Connie Willis’ short story collections, especially Impossible Things. (Her full length novels are also generally good but the short stories are a better introduction IMO)
My 70 year-old mother in law read Forge of God (Greg Bear) and quite enjoyed it; an interesting, realistic look at the Fermi paradox from the point of view of present-day Earth.
Science fantasy is an entirely different species which has little in common with real science fiction, IMO.
SF worldbuilding at
http://www.orionsarm.com/main.html
I’d like to throw in a hearty second (actually, by now, I think it’s a third) for anything by David Brin. Almost all his stories are each set in their own “universe”, so any single book can be read on its own. Even within the Uplift series that godzillatemple mentioned, each book stands alone, more or less – at any rate, the first three certainly do. (I actually read Startide Rising before Sundiver by mistake, and I didn’t feel that I was missing anything.) The second three are meant to be one single storyline, though and should definitely be read together.
Also, his book Kiln People was a great read. Sort of a combination of science fiction with a mystery novel. In addition, The Practice Effect was one of the first books of his I read, and thoroughly enjoyed.
Let’s see, what else have I read…definitely try a few Asimov books. Some are better than others, but I can’t think of any that were remotely “bad” by any stretch of the imagination. 
Nor can you go wrong with Bradbury, from what I remember…it’s been quite a few years since I read any of his books.
I just finished The Moon is a Harsh Mistress and it’s fantastic. Highly recommended.
I also adore Ender’s Game; it’s one of my favorite books of all time. Don’t know how much I’d recommend it for your purposes, though, since it’s not really all that science-fictiony - actually, it’s the classic example of SF-for-people-who-think-they-hate-SF; the aliens are just a MacGuffin, really.
A couple of favourites:
Dancers at the End of Time by Michael Moorcock. A trilogy about decadance and the redeeming power of true love. The characters have godlike powers that they use only to amuse each other, until Jherek Carnelian meets Amelia Underwood, a nice Christian married lady from 1896, and falls in love. Surreal and touching by turns.
Mission of Gravity by Hal Clement. Hard SF, set on a Jupiter-sized planet with a day of (IIRC) 36 minutes. The main character is a native who looks like a squashed centipede. I like him! Good adventure, too.
Read Harlan Ellison. Anything. A Boy and His Dog would be a good place to start. In my opinion, Ellison is the best.
I also second (or third, or whatever we’re up to now) the recommendation for Ender’s Game. The rest of Card’s stuff is worth checking out as well.
I can recommend 3 books that are part of different series but work as stand alone novels.
West of Eden by Harry Harrison. One of the most fully realized nonhuman (they’re not alien) species ever.
Wildseed by Octavia Butler. It’s great for comic book fans because it shows a more realistic look at super powers. Also has great characters.
The Snow Queen by Joan Vinge - A very interesting read for the celestial mechanics of the main planet. If you like this and want to read more, skip the second book World’s End because it’s not very good and everything is recapped in the third book The Summer Queen.
How about Robert Silverberg? He’s one of the most prolific authors in the business and back in the 70’s alone he wrote several classics. Advantages are that most of his books are stand alones, not parts in a series and most are novellas or short novels. Looking over a list of his works, I’d recommend any of the following: Hawksbill Station, Nightwings, Up the Line, The World Inside, The Book of Skulls, Dying Inside, The Stochastic Man, Born With The Dead, Passengers, How It Was When The Past Went Away, Good News From the Vatican, The Pope of the Chimps, Amanda and the Alien, Sailing to Byzantium.
For Asimov, I’d recommend The Caves of Steel as an introduction. It’s sort of smack in the middle of his universe, but stands alone if you only want to read one book.
Or pick up any of a hundred Asimov short story anthologies. Be sure to try out a robot story or ten. I love them, each and every one.
Boy, what a great assignment!!! 
More kudos for “Ender’s Game”. For Brin my suggestion would be “The Postman”. Arthur C. Clarke’s short story collection “The Nine Billion Names of God”. Of the other Masters I’d suggest Asimov’s short story “Nightfall”. Most any Heinlein, but “Stranger…” is a great start. “The Forever War” by Joe Haldeman. “Star Dance” by Spider Robinson (whose “Callahan’s Crosstime Saloon” series is great if you like really bad puns). For a plethora of wonderous authors, check out “The Hugo Award Winners” collection. And check out garage sales or libraries for old issues of “Asimov’s Science Fiction Magazine”. I saw some GREAT writers go thru that wonderful magazine.
There are TONS more, but my time is done.
Welcome to SF geekdom!!
The Amtrak Wars - Patrick Tilley.
Another vote for Ender’s Game, The Postman, anything by Spider Robinson and Kim Stanley Robinson’s Mars books.
I’d also recommend Jack McDevitt’s novels. “Moonfall” is a good introduction, although “Eternity Road” is my favorite. They’re all stand-alone, but there are a few recurring characters, who are extraterrestrial archaeologists.
David Weber’s Honor Harrington novels are excellent as well. Think “Horatio Hornblower” in space! The first is “On Basilisk Station.”
C. J. Cherryh’s “Foreigner” series is another favorite of mine. Her aliens are so real, so fully-developed - I can hardly believe she actually made them up!
And don’t forget Frank Herbert’s “Dune!” The newer “prequels” by Brian Herbert and Kevin J. Anderson are worth reading, too!
Science Fiction is a great genre! Have fun exploring!
I’m also a big fan of C.J. Cherryh.
I cant believe no one has mentioned any of the wonderful sci-fi titles by L Ron Hubbard ;-p
[hit submit/run/hide]