Wikipedia gives the classical definition of an anithero:
What I'm talking about does fit that definition, but what I really want goes a little further. I'm talking about a story that follows the villain, and I don't just want any villain. I want one you can respect; a villain you can root for.
Both of these shows achieve this the same way, with three important characteristics.
1. A villain needs to be dangerous.
2. A villain needs to have earned whatever ability that makes them dangerous.
3. You can't just tell the audience that they earned that ability.
The third is the key, and it's the one that almost everyone overlooks. How many times have you read a story that says that their evil villain is so clever, but then to prove it they point to some past achievement, or some machine he built?
Deathnote has done this better than anything else I've seen. If you're afraid of anime, try to look past that just this once. I swear 90% of people will be hooked after the first two episodes.
And check out Hannibal if you haven't. The world needs more good bad guys.