A Fire Upon the Deep, by Vernor Vinge

Fantastic,fantastic book. The first really original science fiction that I've read in some time. At least two ideas in it that I've never seen anywhere else. The ending is a bit of a jumble, but not terrible.

Highly recommended.