A couple that aren't usually thought of as sci-fi but would be if they were publiished today: "Utopia" by Thomas More, and Swift's "Gulliver's Travels". As far as more modern books go, one of my favorites, for it's great plotting and incredibly prescient imagining of an information web, is "Shockwave Rider", by John Brunner.

About 13.75 billion years ago, actually.