Since there seems to be quite a bit of overlap here already I'd just like to list three authors who haven't been mentioned yet. Extremely highly recommended.
Stanislaw Lem: pretty much everything, but you should start with Cyberiad and His Master's Voice.
Arkady and Boris Strugatsky: First and foremost I recommend Roadside Picnic. (later adapted to the Stalker movie and the Stalker games). Their other books range from decent to great.
Jorge Louis Borges: everything. He was not strictly a sci-fi author but was actually marketed in the Soviet bloc as sci-fi, and justifiably so. I would call him a writer of "philosophy fiction".
I have never read very much Science Fiction, unlike some of the people here on Less Wrong, and I think I would like to. At least, the few books I have read I enjoyed. I've read a couple of books from Asimov's Foundation Series, two Michael Crichton books, Twenty Thousand Leagues Under the Sea by Jules Verne, and an anthology of SciFi short stories (no really famous authors) that my dad owned.
That list looks very short. I just finished reading a fiction book, and am looking to start another. Recommendations? What are the two or three books I simply must read?