Vinge's Marooned in Real Time, A Fire Upon the Deep. The former introduced the idea of the Singularity, the latter gets a lot of fun playing near the edge of it.
Olaf Stapledon: Last and First Men, Star Maker.
Poul Anderson: Brain Wave. What happens if there's a drastic, sudden intelligence increase?
After you've read some science fiction, if you let us know what you've liked, I bet you'll get some more fine-tuned recommendations.
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.
And happy new year to everyone.