Surely you have already seen Perfect Blue? You have to see Memories (for the perception-bending space part). Key The Metal Idol (keeps you guessing). Aeon Flux (not technically anime) is also very good.

I also think it's worth tasking a risk on: Revolutionary Girl Utena (if you can see past the cute girls & bright colours). Full Metal Alchemist (dark but intelligent). Evangelion.

If you are looking to 'branch out' a bit, but still stick to anime aimed at "mature" audiences, then also try these: GTO (Great Teacher Onizuka), Planetes (v.realistic), Initial D (actually a very intelligent series), Black Heaven, Gokusen (just ignore the stupid dog), and maybe Big O (the ending of series 2 will mess with your head).