I watch too much anime for my own good. I'll try my best to narrow it down.
Code Geass is a MUST. Its one of a kind in its genre and everything about it is awesome. It does involve some mechs, but the execution makes the series one of the best I've seen to date.
Gunslinger Girls is not too bad as well since you've seen Lain and Kino. Brainwashed, or 'conditioned' girls trained to kill in undercover missions, supervised by their caretaker (forgot the term used in the series). Googling it will probably give you a better description than I am right now ^^;
Paranoia Agent is pretty good too. It is done by the same production team who made Paprika.
You could jump to the popular Shonen Jump series such as Death Note, Naruto, One Piece, and Bleach and enjoy their manga-anime counterparts. I recommend Claymore.
Original anime series are getting popular these days. Including Speed Grapher, Darker than Black, Romeo x Juliet, Blood+, Eureka Seven are a few. These however can be a hit and miss for some (Darker than Black is bi-episodic, while the animation in Blood+ and Eureka Seven is inconsistent from episode to episode. Romeo x Juliet I just plain didn't like.)
Angelic Layer was awesome. It is about a girl who gets into the world of the game Angelic Layer, where dolls a Deus creates battle each other. I was really obsessed with it for a while and I would recommend a look-see. CLAMP is behind the story concept and there is a 5 volume manga series.