Unlike Star Wars, Indiana Jones and Batman, Dune lost some of it's rich complexity when translated to Lego.
I read Dune Messiah in the fall of last year, just a couple months after reading Dune, and it struck me as little more than an extended epilogue to the story which hand already unfolded. It didn't introduce any terribly compelling new characters or convincing threats (Sorry Scytale, you just aren't as cool as your name suggests). Herbert did introduce Ghola cloning technology to the series, but left the concept rather under-explored. That being said, the story does bring added closure to the original, and it brings it very well, beggining with the backlash to Paul's assendency and continuing on to his tragic fate.
I say Children of Dune is a proper sequel, because it runs counter to the first two books in almost every way. The energy dedicated to exploring Paul's ability to predict the future has been redistributed to his children's genetic total recall. Paul's heroic decision to die a mortal death and avert intergalactic Jihad is reconstrued as an act of selfish cowardice. It is revealed that Paul didn't even die at all when he walked off into the desert. Even though the plot twist initially excited me, (for it's hard not to get excited about characters coming back from the dead), I was it left me sad later on, because it's the sort of inorganic story telling Herbert never resorted to in his earlier novels. Admittedly, he does soften the effect of this revelation by repeatedly foreshadowing it and repeatedly stressing that Paul has become a different character, but it still feels like some sort of cheap trick.
Sadly, this is not the most preposterous plot point in Children of Dune. Characters who have been well established as intelligent and wise suddenly suffer from attacks of idiocy, only to display mind boggling insight moments later. Lady Jessica is a prime example. Even though Leto II (Paul's son and the new protagonist) makes her look like an idiot fool in conversation, she somehow mannaged to see past his elaborate feign death and trap him in the desert, even though he is presient and she is not. More messily developed characters like Alia and Duncan (or the Ghola formerly known as Hayt) spiral out of control destroying the few consistent threads of personality which had been previously established. These gaping holes in logic and continuity detract from the wonderfully density Herbert's world displayed in the first book. Even though we have lots of plots twisting around eachother and tangling together like sound trout, they never quite form a worm, or a god-emperor for that matter.
Fortunately, Herbert's philosophical musings remain poetic and potent, and conceptually he continues to engage. I resonate with the book's central message, assuming I correctly understand it to be the sentiment that people are far too eager to submit themselves to the will of heredity. At the same time the Golden Path, Leto II's infallible plan to ensure the survival of the human race, strikes me as an inherently evil concept because it is contingent upon the idea that man must submit to the rule of a single godly tyrant. Indeed, Paul deliberately avoided such a path in the first book for the same reason. Leto denounces this is cowardice, since Paul created a universe that looked for divine justice by becoming a messiah, only to deprive it of such guidence. While I'm willing to concede that Paul's suicide may not have been the best decision for his empire, Leto never provides a convincing explanation as to why tyranny is a better alternative.
In fact, the end of Children of Dune serves as a dark reflection of the original novel's conclusion; the main character storms into his enemies lair, laying waste to all resistance, and coerces the survivors into submission, though for some reason when Leto did it, I felt like evil had won. I think my primariy problem is a lack of motivation. Paul was finally attaining retribution against the Harkonens who had killed his father and brutalized the people of Arrakis, while Leto (who didn't feel human even before merging with worms) is simply killing his demented aunt. The fact that he claimed his sister for a wife and whored her out to his cousin doesn't sit well with me either.
On the pluse side, Leto is primed to be a brilliant villian in God Emperor of Dune, though I think it will be a good long while before I head back to Arrakis.