I second the recommendations of 1984 and Player of Games (the whole Culture series is good, but that one especially held my interest).

Recommendations I didn't see when skimming the thread:

• The Hitchhiker's Guide to the Galaxy series by Douglas Adams: A truly enjoyable classic sci-fi series, spanning the length of the galaxy and the course of human history.
• Timescape by Gregory Benford: Very realistic and well-written story about sending information back in time. The author is an astrophysicist, and knows his stuff.
• The Andromeda Strain, Sphere, Timeline, Prey, and Next by Michael Crichton: These are his best sci-fi works, aimed at realism and dealing with the consequences of new technology or discovery.
• Replay by Ken Grimwood: A man is given the chance to relive his life. A stirring tale with several twists.
• The Commonwealth Saga and The Void Trilogy by Peter F. Hamilton: Superb space opera, in which humanity has colonized the stars via traversable wormholes, and gained immortality via rejuvenation technology. The trilogy takes place a thousand years after the saga, but with several of the same characters.
• The Talents series and the Tower and Hive series by Anne McCaffrey: These novels deal with the emergence and organization of humans with "psychic" abilities (telekinesis, telepathy, teleportation, and so forth). The first series takes place roughly in the present day, the second far in the future on multiple planets.
• Priscilla Hutchins series and Alex Benedict series by Jack McDevitt: Two series, unrelated, both examining how humans might explore the galaxy and what they might find (many relics of ancient civilizations, and a few alien races still living). The former takes place in the relatively near future, while the latter takes place millennia in the future.
• Hyperion Cantos by Dan Simmons: An epic space opera dealing heavily with singularity-related concepts such as AI and human bio-modification, as well as time travel and religious conflict.
• Otherland series by Tad Williams: In the near future, full virtual reality has been developed. The story moves through a plethora of virtual environments, many drawn from classic literature.

Edit: I have just now realized, after writing all of this out, that this is the open thread for January 2010 rather than January 2011. Oh well.