I second A Fire Upon the Deep (and anything by Vinge, but A Fire Upon the Deep is my favorite). BTW, it contains what is in retrospect a clear reference to the FAI problem. See http://books.google.com/books?id=UGAKB3r0sZQC&lpg=PA400&ots=VBrKocfTHM&dq=%22fast%20burn%20transcendence%22&pg=PA400
If anyone read it for the first time recently, I'm curious what you think of the Usenet references. Those were my favorite parts of the book when I first read it.
I thought the Usenet references were really cool and really clever, both from a reader's standpoint, and also from an author's standpoint. For example, it doesn't take a lot of digression to explain it or anything since most readers are already familiar with similar stuff (e.g., Usenet.) It also just seems really plausible as a form of universe-scale "telegram" communication, so I think it works great for the story. Implausibility just ruins science fiction for me, it destroys that crucial suspension of disbelief.
And happy new year to everyone.