Anything by Neal Stephenson is good, especially Snow Crash and The Diamond Age. His work is characterized by very detailed, interesting settings.
For sheer scale and mind-bendingness, I haven't seen anything better than City at the End of Time, by Greg Bear. It's got a 100 trillion year old civilization with very alien culture, in a disturbingly weird universe.
Cryptonomicon is indeed a masterpiece; the author's arrogant and pushy but I like how humanist he is.
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?