I only watch dubs because i think you get more connection to the characters and plot if they're speaking your language so i can't comment on the Japanese audio of the following but the English versions are rank as some of my favourites that i think you may like. Contrary to you i didn't think much of Elfen Lied...try these (although i have a hard time grasping Japanese classifications of anime so if i hit a shonen anime i've no idea that i did so) I won't rescan this entire topic but i'd say you've definitely been recommended some of these already...
The Melancholy of Haruhi Suzimya is probably my favourite anime probably because of the characters themselves. I even loved the "difficult" sequence in season 2.
Planetes is another great tale with fantastic characterisations
Baccano - somewhat difficult to get your head around because it's nonlinear but it's a fantastic set of plots and characters
Durarara - same as Baccano but more straightforward. Kari Wahlgren's acting in this really sold me on the emotional tie, especially the final monologue.
Beck Mongolian Chop Squad - best music anime out there
Great Teacher Onizuka - this is one of those weird anime's where you start off unimpressed with it but after a few episodes (i think it was number 9 with me) you realise that it's actually brilliant. The characters really come to life. If you watched the dub of Bebop then the same guy voices Onizuka in this (Steve Blum)...no idea if that's true of the Japanese va (probably not)
More "actiony"
Ga Rei Zero - Kind of dark and pretty fast paced
Corpse Princess - sort of like the above but longer
Canaan - i really liked this but you might like it less. It's better than Elfen Lied though.
Black Lagoon - ditto the above. Revy is awesome though.
Birdy the Mighty Decode - another i really loved although it seems more hit and miss. It's a nice blend of sci-fi with slice of life
and on a limb (since this is a gaming forum) The Aegis of Druaga and the Sword of Druaga. An anime based loosely on the videogame but it plays fast and loose with it. The first episode is golden so if you hate that maybe this isn't for you.
Ah I've been meaning to see Haruhi actually.. And Planetes and Baccano Thanks for the other suggestions.