My only complaint about the first two books is that the titles are so similar that I have to think about the difference between the Deep and a deepness, within this universe, in order to remember which is which. Vinge's only helping me a little on this front, when it comes to the latest novel's name. Oh well.
If you are wondering why I've used the "dogs" subject tag on this post, well, you need to read AFUTD to find out.
Incidentally, Vinge's unrelated novel, Marooned in Real Time, is also among my favorites. I'm currently "reading" Rainbows End via audiobook, and just this morning, I heard a fourth-wall-breaking throwaway reference to the Tines and the Unthinking Depths. Hilarious.