soft hearted alert!!! Noein is my fav of the bunch. those music themes+emotional moments, even though I didn't like the drawing style, it really made my melancholia level go to 11.
don't know for dennou coil's complexity though, it's google glasses with extra steps. but I certainly liked the silly candid stuff in it, from the dog to the the antivirus. I had "boku saachi, youroshiku ne!" as sound alert on IRC for almost a decade(my other sound alerts were from GITS because I'm worth it).
@Love Music. do you mean complex plots even if the rest is basic(like say Death Note with real battle of wits, but not much else), or do you lean more toward complex environments and fancy dystopia? because I don't think something like coboy bebop has a complex plot at all. they just have adventures with little to no relation between the various events beside trying to make a buck and get something to eat ^_^.
about Code Geass, what is it you didn't like? mecha? the oldschool Japanese love for European classics? the cheat power? depending on what you like, the suggestion could be vastly different. personally I'm a little like
@kn19h7, among your list, some are obvious winners for me, but some didn't do much for me. so there's a need for specificity IMO. D gray man maybe? I don't know how far the anime goes into the manga story, but if we're talking about overly complicated, that seems like a hit. when I think about Serial experiment Lain, somehow I also think about Paranoia agent. not sure you'd see a relation beside being F in the head in a strangely enticing way. ^_^
Mirai NikKi might be something you like, I personally didn't, but it's pretty complicated in various ways. I'm not sure I can make the distinction between mystery planted artificially and complexity in a plot when I'm considering animes. I've never been very good with placing art into boxes. is Deadman Wonderland a complex plot? or just some fake stuff added to give a context to good old battle royal?
anyway you've already seen the true complex plots animes, which aren't many. even beyond the notion of anime being for kids, intricate concepts aren't that common, even in movies they aren't IMO. I'd throw in Last exile, because I'm a total fan, but IDK if the plot is that complex, it's more like the the story ends up involving people with more complicated backgrounds. otherwise it's pretty much about kids who like to fly some weird planes without wings. sort of Anakin Skywalker as a kid. IDK