^ Guck dir auf jeden Fall mal Black Lagoon an. Alles in allem ist es ziemlich genau das, was du in deinem Post beschrieben hast (auch wenn die Stimmung nicht so düster ist wie in Watchmen). Bzgl. der Charaktere muss ich allerdings vorwarnen: auf den ersten Blick sehen sie alle irgendwie ziemlich nach den genannten Typen aus (auch wenn statt "hilfloses Schulmädchen" "hilfloser Büroangestellter" treffender wäre). Ab etwa der Hälfte der ersten Staffel (also um Folge 6-7 rum, wenn ich mich recht entsinne) ändert sich das aber, versprochen.
Elfen Lied solltest du dir weiter ansehen. Die erste Folge ist, wenn ich mich richtig erinnere, die schlimmste, danach wird es angenehmer (auch wenn Lucy fast die ganze Zeit etwas psychopathisch veranlagt bleibt).
Ich würde noch Hellsing (sowohl die TV-Serie als auch die Hellsing Ultimate OVA) empfehlen, aber du magst ja offenbar nicht, wenn es allzu blutig ist. Schade, denn zumindest die OVA ist wirklich gut (auch wenn Alucard jetzt nicht soooo viele Facetten aufzuweisen hat… er ist so badass, dass da für andere facetten kein Platz bleibt ;)).
Des weiteren gibt es da noch Spice & Wolf. Der geht in ne komplett andere richtung als die oben genannten, aber einen erwachseneren Anime als diesen wirst du wohl kaum finden. Der Plot besteht darin, dass ein Kaufmann in einer mittelalterlichen Welt umherreist und versucht auf legalem Weg reich zu werden. Ab und zu gibt es ein bisschen Action (Räuber, Wölfe, etc.), aber im großen und ganzen ist er unheimlich trocken, und der einzige Grund ihn zu gucken wären wohl die unglaublich vielschichtigen Charaktere.
Ansonsten solltest du dir noch Mahou Shoujo Madoka Magica, Mahou Shoujo Lyrical Nanoha (alle drei Staffeln), Samurai Champloo, Cowboy Bebop, Accel World (der Hauptcharakter hier ist etwas nervig, sei gewarnt), Bakemonogatari (und die Fortsetzung Nisemonogatari), Kannazuki no Miko, Noir, Madlax, Shingeki no Kyojin, Steins;Gate und eventuell Panty & Stocking with Garterbelt (für die Lulz) angucken, ob die evtl. was für dich sind. Die meisten davon passen vom Genre, die anderen sind einfach was ich dachte, was dir eventuell noch gefallen könnte – tut mir leid, falls ich mit irgendwas daneben liegen sollte ;)