I'm sure these have already come up, but I'll add my voice in enthusiastically recommending the following -
Accelerando will have rather familiar themes and ideas to anyone who's spent significant time on LW, in particular, although that goes for the others to a slightly lesser extent. City at the End of Time was probably the most "work" for me to read out of the four - I enjoyed it greatly, but it's a book best savored slowly. Neuromancer is pretty much the grand icon of cyberpunk, and Gibson's facility with densely evocative language makes me jealous. The Diamond Age is probably the one I had the most lighthearted fun in reading, the easiest to follow, even though it's a very thought-provoking story.
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?