I've just finished reading A Fire Upon the Deep and A Deepness in the Sky. I'm just about twenty years late to the party here, but the part where I missed just about everything published between 1985 and 2004 is a known bug, patch in works. I'm mentioning my tardy party attendance because I know I'm not the only one to have missed these two particular books, and that's a shame. They're excellent.
A Fire Upon the Deep is the book I was 40 pages into when I had the book-lust crisis over my shiny new copy of Name of the Wind. The tie-breaker gave it to the book I hadn't read before, and I'm pleased. A Fire Upon the Deep is smart and entertaining in the immersive, fleshed-out way of books that aren't just fun, but rich. There's a subtlety of world building here that's missing, say, from Moon's Vatta's War series, though I tore through that at a similar pace. Vinge's real accomplishment, the one it takes reading it for the first time twenty years later to notice, is that his conception of the internet is 1992's, with text-based message boards, and the world was built so well that I believed a far post-singularity future would have a less mature network. I was convinced enough of the distances between places, of the alienness of the aliens, of the physical limits of his worldd that running across future bandwidth that makes late-stage dial-up look rapid didn't throw me out of the world. And I'm told my tolerance for that kind of world breaking is absurdly low.
The key to that particular coup is in how excellently Vinge manages to create aliens who feel truly, convincingly other, and immerse the reader in them so far they stop feeling strange. He does this better with the Skroderiders and Tines in Fire than with the Spiders in Sky, but both books do it well. To take the Skroderiders as an example (because figuring out the Tines was what hooked me and I don't want to spoil that experience for the folk I'm persuading), these are sentient trees grafted onto a low-level AI and automated cart, who wander around the universe as traders. Out of context the idea is absurd and comical, and he doesn't neglect the absurdity or comedic reality of the characters, but by giving them, if you'll forgive me, roots that tie them into the larger universe, a sense of culture (some of them opt to just hang out as sentient trees, there are rumors that others go in for the Singularity chasing but nobody likes to mention it), and most importantly, a sense of believable body language, I swallow the whole idea without blinking. The Tines are even nuttier, and he sells them even better.
Let's pause for a moment and quibble over something that's been grating me since noticing it on the cover of Sky, i.e. the assertion that these books are Hard SF. The cover quote is something like, "Everything a hard SF fan could want." These books are not hard SF, they're space opera doing a phenomenal impression of hard SF. How do I know? Because when I read hard SF, I walk away knowing how their FTL works, the design specs of their ships, and in one memorable case, finally know what the hell a logarithm is. Vinge doesn't bother to share any of those details, which is great because I don't care about them. What people mean when they say these are hard SF is that the world is detailed, consistent, and he saves his technological handwaving for the climax where you're so invested in the characters who are so invested in what's happening that I'm probably the only person in the world who cares that hands were waving, and I didn't care until the book was over. These books were marketed as hard SF because the 90's were the years when you couldn't get less sexy than space opera, a sub-genre making a slow but steady recovery.
While I'm ranting about space opera, there are two kinds; the sort where everything feels like the future, and the kind where it feels too old and almost reads as the past. One notable example of the latter case went ahead and claimed it was all long, long ago in a galaxy far, far away. Dune would be a more reputable example of the latter case. The previously mentioned Vatta's War series is the former case - I read the whole series as being set in brightly lit white rooms with clean lines, even when that wasn't true at all. Fire and Sky feel old. It's definitely the future, but a future with so much history that cares so little about our civilization as it exists now, or even then, that it reads like a real epic, a tale of adventures from the glorious past and don't we all wish we'd been there when things were cool. This is probably a personal quirk, but so's everything since I started talking about genre.
Back to the main subject, I want to correct another assertion I've heard bantered about, that you can read these two books in either order because they don't have much to do with each other. This is technically true, but don't believe it. Pham Nuwen is allegedly a character in common across both books, but he clearly didn't get the development we see in Sky until Vinge sat down to write the second book. The character outlines are the same, Qeng Ho trader rescued from medieval planet of Canberra, went on to kick ass, but he's so much richer, carries so much more depth in Sky and running into the flimsier, enigmatic version of him we see in Fire could only be frustrating. If that's the sort of thing that will trip you, read them in the order they were published.
On the other hand, Sky is the weaker book, though not remotely weak. Vinge does a thing about which I'll remain vague to explain how we're getting the Spider's POV, and when he reveals it I got kicked out of immersive-reader mode and into meta-reader mode. I like meta-reader mode, the majority of the crap epic fantasy I've read and enjoyed got gobbled in meta-reader mode, but immersive-reader mode is vastly more satisfying and the switch hurt. It was a momentary lapse, and the only time either book kicked me, but it hurt, in part because I'd been so immersed. To give you perspective, the book is over 600 pages and I'm whining about something that bothered me for half a page, but it did happen. I mention it because it ties into the other weakness of the book, that the Spiders were never as alien as the Tines or the Skroderiders. That makes sense from a world-building perspective, the Spiders are much closer in to natural human space, but it also meant I didn't get the same satisfaction out of my intimacy with them. I got a lot more mileage out of learning about the Emergents and their culture, and even that sussed out to "Fascio-collectivist government, check." I think these were all choices Vinge made, these details were nearly as important to the story being told in Sky than they were in Fire, but I felt their absence. It's possible that reading these back-to-back isn't a good idea.
I've got mixed feelings about the endings of both books. Without going into spoilery details, I felt like the end of Fire was too easy and Sky was too neat, even though that's not really true in either case. This is either a consequence of Vinge wincing at the last moment, of standard beginnings get more work than endings writerly-practice, or of me picking up on subtle signals that left me expecting or wanting something a couple degrees off from what I got. It's the sort of thing that didn't really blemish the reading experience for me at all (as mentioned, there was but one blemish), but which taint the post-reading reflection.* It's the kind of thing I really want to argue about with somebody who disagrees with me.
But I'll need somebody who's read them to do that. So go read them, okay?
*Many books I don't have much trouble with finishing, then turning around and picking up the next thing. That wasn't true for Sky and probably wouldn't have been true for Fire if I weren't picking up its sequel. Switching from Sky to Swordspoint did not work. Don't try it.