It's been so very long since I first read A Fire Upon A Deep that it's almost like reading a fresh book. As Ari mentioned, the aliens are very alien, which itself leads to a phenomena where the human protagonists are aliens, too.

I'm slowed a bit because I've gone back to re-read short passages a few times. The narrator's voice is so firmly in control that sometimes it's actually a little distracting for me.