I honestly feel that the best animes that I ever saw on my foray into anime back in my teenage years was from the early 2000s like the ones we mentioned already (Ergo Proxy, Texhnolyze) and others like Serial Experiments Lain, Gungrave, Witch Hunter Robin, Paprika, Perfect Blue (lates 90s but still), Monster and the list goes on and on. I really liked the darker anime stuff like that. Not as much of it nowadays for me as back then (the art styles were more my style back then too). So much anime that felt more aimed at older audiences (not just for teens) and respected the intelligence of the viewer without as many cliches throughout (and if they had them, they were well done regardless). I don't think any of those animes get the recognition they deserve.
Anyway, this is really off topic now, so I'd better stop. NieR is fucking great. There we go.