Excession

If you are not reading Iain M. Banks' Culture novels, you are seriously missing out.  Many people I have discussed them with are turned off by the notion that there is one pan-human force in the universe that is all-knowing and capable of dealing with any potential threat the universe can throw their way, and if that idea sounds boring to you, I highly recommend you begin the Culture series with Excession as your introduction, and revisit Consider Phlebas later on.  The title implies the conflict -- what happens when the Culture encounters a force so completely beyond their comprehension that is exceeds all known explanations?  Even the highly advanced Minds housed in Culture ships cannot begin to fathom what this mysterious spherical object is that appeared out of nowhere at the edge of space.  Such a rare and thus far never before encountered object is clearly valuable, and the Culture must battle another alien race called the Affront that refused to assimilate into the Culture long ago.
The horror in this novel can be found in the Affront culture. The Affront are without a doubt intelligent, but the Culture finds their barbaric experiments with genetic engineering utterly deplorable. 
The real delight in this novel is found between the interactions of the Culture ships.  Every ship has a Mind with a unique (and often plucky) personality, and this novel provides a great deal of information about ship Minds that is missing from his earlier novels.  The Minds possess not only a fantastic intellect, but a biting wit that will not be tempered by their pan-human commanders (and nor would they want to).