The Left Hand of DarknessUrsula K. Le GuinLe Guin's classic showcases her astonishing imagination and her often forgotten storytelling ability. An everyday interstellar story of boy meets boy who turns into girl. (Yes, I'm oversimplifying a bit). I like most of her early work, as well as some of her later books for young adults, e.g. the Earthsea series (excluding Tehanu).
Consider PhlebasIain M. BanksI like me some space opera, and this is among the best. Superb opening. Horza is a great hero/anti hero. Down with the Culture! Player of Games is also good. But much of Banks other scifi is self indulgent and/or slow.
The Reality Dysfunction (UK style edition)Peter F. HamiltonThis 1100 page behemoth is space opera par excellence, encompassing themes of death, religion, colonization and experience of the utterly alien. Unfortunately, it's something of a "one hit wonder" - the two massive volumes that conclude the "Night's Dawn" trilogy (Neutronium Alchemist and Naked God) are very slow, and I could not even finish Hamilton's Pandora's Star. Which is more than a pity, almost a tragedy - since if I had to pick one book from this list, it would probably be this one. The baffling nature of creativity, I guess!
Great Sky RiverGregory BenfordAlmost slap bang in the middle of a fairly ordinary 6 book series (the Galactic Center series) comes this gem. It is the story of the struggle of far future "post humans" against a mechanized foe with highly sophisticated AI. Often incredibly bleak and moving. Like the Reality Dysfunction, it can and should be read on its own. Benford's Timescape is also very strong.
Snow CrashNeal StephensonStephenson's masterpiece of cyberpunk convincingly depicts a virtual world (the "Metaverse", the acknowledged inspiration for "Second Life") where the citizens of the future play. And something wicked is loose in it. Among Stephenson's other works, I would also recommend Diamond Age and Cryptonomicon, though not to the same extent.
Never Let Me GoKazuo IshiguroIshiguro's superb "meditation on mortality" often reads like SF, and yet has been justifiably superbly reviewed and viewed by many as a classic not just in SF but in literature as a whole. Could be that Ishiguru's record gave him credibility, but SF boosters must also face the possibility that the reason SF is not taken seriously is not prejudice, but because it is mainly crap. When a serious author writes a beautiful SF or SF-style book like this, it is indeed taken seriously.
The Anubis GatesTim PowersSomething of a guilty pleasure: this is a time travel yarn that is notable mainly for its blistering pace, extreme charm and somewhat far-fetched plot. Powers has attempted other similar works, but never reached the transcendent heights of silliness and narrative drive that he achieves here. A modest masterpiece. Also one of a very short list of fantasy novels with Samuel Taylor Coleridge and Lord Byron in the cast!
Altered CarbonRichard MorganPerhaps also a slightly guilty pleasure: but Morgan is a better writer and this debut novel reads like the distilled essence of 30 years thought made into a fine and beautiful instrument. However, it is extremely violent and not for everyone. Basically a noir gumshoe tale set in the far future, where death can be prevented by storing memories in an altered carbon "stack" at the base of the skull. Of course, that's provided you have enough money to purchase a new body or "sleeve". Protagonist Takeshi Kovacs returns to less effect in Morgan's later novels, Broken Angels and Winged Furies.

Bubbling Under
HOUSE OF SUNSby Alastair ReynoldsThe book you knew he could write.
EVOLUTION'S DARLINGby Scott WesterfeldOf all the losses from SF to YA, Westerfeld must be one of the biggest.