⭐⭐⭐⭐
Short review:
An improvement from book 1 and a true taste of the rest of the series.
Long review:
I had almost written off Steven Erikson's Malazan epic after reading "Gardens of the Moon", which I thought was mired in D&D tropes, boggled down by cookie-cutter characters and overstuffed with information and world-building that seemed interesting but hard to grasp.
It's a good thing that I gave the next book in the series a chance. The characters are better fleshed out in this book, which benefits from a few new characters and a somewhat clearer plot (at least one of its threads, that of Coltaine and his Chain of Dogs which I felt was the stronger and best-plotted thread in the series so far). Duiker and Heboric are more rounded characters than Paran and the rest introduced in Gardens, though Felisin is a strange character, as she goes from 'easily relatable' to 'unbearable bitch' to 'wise Seer' in what seems hardly believable. Her transition could have been handled better, but it's still a better progression than Apsalar's or Crokus', who showed up as horribly stupid and stereotypical characters in the previous book and aren't given much more to do in this one.
Kalam is starting to become the most interesting character in the series, along with Quick Ben, and the other intriguing parts are the blossoming storylines of the Jhagut, T'lan Imass, Tiste Andi, etc. I expect the author's 'archeological' take on world-building (that is, what I believe he's doing, basically cutting down on exposition for the sake of the reader slowly peeling back layer by layer of the world's history) will end up paying off further down the saga. Icarium's storyline, though, seems important at first but ends up overwhelming. I don't know if I'd be glad to see him appear on a later book, but we'll see.
The best part of Deadhouse Gates is, in my mind, Duiker's progression from historian back to soldier. That whole part of the book was very well handled and the ending was terrific. Too bad Erikson felt he needed to undercut that storyline by adding a final magical macguffin to allow him to have the cake and eat it too.
Overall, a satisfying, fast-reading experience that improves on the previous book's failings a bit.