IMHO the book that best elevates the story is God Emperor of Dune. I think it did a very good job of "I'll deliberately act like a villain so you all hate me, because that's for your own good" thing.
God Emperor is fantastic too, for that reason and others. I would draw a parallel between
Messiah and
God Emperor. The ideas explored in
Messiah were already present in the first novel, but there they are somewhat overwhelmed by its triumphant conclusion, i.e. Paul breaching the Shield Wall on the back of Shai-Hulud and ascending the throne. In that sense,
Messiah isn't so much a left-turn as the necessary carrying to fruition of what was always implicit in the tale. Similarly,
God Emperor explores in greater detail the themes of long-term consequences and change over time that were always part of
Dune, particularly in the form of the Bene Gesserit, who famously consider themselves as acting in the long-term interests of humanity. By the time
God Emperor rolls around, Leto despises the Bene Gesserit because they have failed to live up to their ideals, preferring instead to perpetuate their own comfortable existence, and in doing so have condemned him to pick up the slack instead. The character and fate of Darwi Odrade in
Heretics and
Chapter House is a response to that critique.