I somewhat enjoyed Death Note, but there were two major problems that irritated me a lot about it, both of which are also shared with Code Geass which is pretty similar in the way it presents the story.
First is constantly spelling out every little thought, intention, motivation... well, everything really. It dumbs the storytelling down
immensely. I know not everybody has the patience or intelligence to follow a good detective story, but you don't have to kill the intrigue outright by constantly explaining everything without giving viewer a slightest chance to come up an explanation on their own. Arthur Conan Doyle knew how to work with this problem; he solved it brilliantly by introducing Watson, a character with intelligence considerably lower than Holmes's but pretty close to the more observant half of the presumed reader/watcher audience. So when Holmes would deduce something really tricky he would usually ask Watson for his own analysis first so that we, the audience, would first be able to compare our thoughts on the matter with those of our equal, instead of being constantly spoon-fed with logical chains so delightfully obscure they feel completely detached from reality... like it happens in both DN and CG all the damn time.
My second gripe with DN is writers taking so much drugs coming up with dramatic problems and even more dramatic, almost deus ex machina-ish solutions, it breaks suspension of disbelief in half around episode 17.
You think you got me now, huh? But I have foreseen you having foreseen me having foreseen how you thought I thought you thought I would act, so I'll do something different and possibly completely unrelated! *groan* Do the characters read the script in advance, like the Joker in The Dark Knight? Why do they always rely on something completely unrealistic, so that it always feels like they just know it's going to work despite the odds, just because the authors want that? Or introduce new characters at an arbitrary point in the story just to hold everything together? Meh.
That being said, if you're up for watching it, I would at least recommend grabbing fansubs by Subbers in the Rye. By far the best release you can find.
So what are the cleverer, more coherent story-driven anime shows/movies, anyway? I mean those that have strongly written, engaging story above all, and not just cool characters or unusual storytelling. Given it's mostly a commercial industry that caters mostly to the inane side of the spectrum—that's where the money is—who are easy to please with the cheapest tricks (not necessarily a bad thing if done tastefully, mind you), one has to dig pretty deeply to find gems unconventional not only in style, but also in essence. People often mention Monster and Legend of the Galactic Heroes as some of the best examples, but sadly I haven't gotten around to either of them yet; hopefully I will soon. Off the top of my head I would name
Satoshi Kon, and
Katsuhiro Otomo as the major brains behind anime screenplays (well,
this guy to a large extent, too, but he's virtually unknown). I can't say everything they have made is genius, but it's still ranging from well above average to exceptionally good.