The Torturer series by Gene Wolfe, followed by The Long Sun series, followed by the Short Sun series.
The Knight Wizard pair (Wolfe). In either order, but both. I started with The Knight, which was the first to be published.
Almost anything by Ursula K Le Guin. Especially those from before 2000. For a series: The Earthsea Cycle. Note that pub dates are misleading, since most of her work has been republished.
Ringworld (Larry Niven) and its sequels (they fall off a bit as it goes on, though). Lots of other stuff by Niven.
Foundation, by Asimov, though it disappointed me. I actually had the opportunity to argue a bit of this with him once. Funny story. I didn't care for the ending of Foundation and Earth
(I think it was) and told him why. His wife, who was sitting next to him, turned to him and said, "I told you so!". Made my day.
The Robot Series by Asimov. Is AI really life?
Dune (first couple of volumes anyway) by Herbert. When it gets boring, quit. It will get worse. For me it was an exponential fall-off. The first chapter better than the average of the first book. The first book better than anything that followed, etc. But it starts out HUGE.
Ender's Game, Orson Scott Card. Note that there is a boycott on Card's work due to some of his extremest statements about LGBT folk. Entirely too much of that going 'round. I prefer not to give him money, but your local library already has. His views don't show through much in these books. (I don't remember that they did at all, actually). Le Guin's views show through clearly, but they are better views. The reason I suggested the early stuff is that she gets a bit strident and less subtle as time goes on. The views are still good (in my view), but the books less interesting.
Brave New World, Huxley
1984, Orwell. I wrote a college paper once comparing these two. The original paper got an A. The follow up, an F. Go figure. I worked harder on the second, but lost insight.
Explore for yourself at http://www.goodreads.com/genres/science-fiction
The Helliconia Series by Brian Aldiss. Not entirely unrelated to some things said here (OTT) already.
Anything by Neil Gaiman
I find anything involving two-way time travel to be extremely boring. There are few problems you can't solve if you can go back and change history. Exciting shoot-em ups, but no real tension.
Nearly anything by C. J. Cherryh. She does both fantasy and scifi, but doesn't herself think there is a difference. Her TrueName is Cherry, but her publisher made her change it, thinking no one would take her seriously. Take her seriously. I found Gate of Iverel (Morgaine Series) to be wonderful.
The Tom Rynosseros series by Terry Dowling is absolutely first rate. Best read in order. They are hard to find, published in Australia. Lots of interleaving threads including AI, desert travel, alternate history... Marvelous.
Natural History, by Justina Robson. Funny too.
I don't need to mention Harry Potter, Discworld, LotR, of course.
Leaving scifi behind, anything by Jorge Amado (historical stuff from Brazil) or Gabriel García Márquez (especially One Hundred Years of Solitude, and Love in the Time of Cholera.)
There is a new translation (in English) Iliad that is a marvelous read.
Captain Horatio Hornblower. One of my favorite series as a kid. Hornblower rises through the ranks during the Napoleonic wars.