In contrast with most of the opinions here, I prefer Fire Upon the Deep. I think the alien species it explores is much more interestingly non-human than the one in Deepness in the Sky and that the bad guys in Deepness are kind of comically over-done. They suffer from a common problem where the bad guys have to not only be bad for main reason X but also are sadistic rapists, torturers, etc. on top. As if we didn't already get the "they're bad" memo already. Plus all the action happens in the finale and, to a large extent, outside of our view. Still, both are great books, but I'd recommend Fire to anyone first.