Given the OP’s apparent tastes, I would particularly recommend Crimson’s latest, The Power to Believe.
Another band worth checking out is Gentle Giant: prog rock they may be, but “wanky” they are not, and they have complexity in spades. Try Octopus, Free Hand, Interview or the live Playing the Fool for starters.
I recommend Dismemberment Plan. Kind of emo, but they have some real talent. Listen to their technique. They’ve got a lot of layered things going on than just the quirkiness. Every time I listen to their stuff I pick up something new.
Early Phish is much the same way. Nowadays they kind of phone in their jam band riffs, but early albums like Picture of Nectar and Rift are amazing. They did a lot of smooth chord and timing changes in those days.
Government Mule may sound like Southern Rock at the outset, but their stuff is actually quite amazing. They are some incredibly talented musicians. Life Before Insanity and the 2 Deep End Volumes are my favorites.
Mr. Bungle’s Mike Patton has a zillion side projects. One you might like is Tomahawk. Also look up Disco Biscuit, Soul Coughing, and Oysterhead.
No question:
This band will blow all minds.
They are metal, jazz, rock, surf, gypsy…everything.
Estradasphere is wonderful! And they’re geeky enough to cover video game theme songs too, which is a nice bonus point in my book. Their version of the Super Mario Bros. 2 theme is my favorite cover song of all time.
I’ll second the vote for the Flaming Lips, although based on the admittedly limited experience I’ve had with them, they don’t quite top Radiohead, and don’t begin to approach the stratospheric genius that is OK Computer. Just my personal opinion, though- YMMV.
And You Will Know Us By the Trail of Dead is quite good, as well. I bought “Source Tags & Codes” on a whim a month ago, and enjoy it a lot. They play very raw, driving rock mixed with some very catchy guitar licks. Their two lead singers switch between vox/guitar and drums, oddly enough.
Aloha is another great indie rock band that I just got into this past year. Ethereal guitar, languid bass, tremendously creative drumming, and a 5-stick wielding vibraphonist.
Sleater-Kinney is also great, so long as you like Corin Tucker’s banshee wail and don’t mind the lack of a bass guitar. “One Beat,” their latest record, is fantastic.
Death is usually the first example given of a technical metal band. Spiral Architect comes to mind.
The latest album by Iris is good, textured electronic stuff. You may not like it - it’s pretty synthpopish. Still good and complex, though!
How about the Pixies? Extremely innovative music that still rocks. I’d suggest Doolittle as a good starting point.
Meat Puppets - Up On The Sun
The Minutemen - Double Nickels on the Dime / Ballot Result / 3 Way Tie For Last
also anything by their bass player, Mike Watt, is worth a listen
Calexico - The Black Light
Giant Sand - Chore of Enchantment
and pretty much anything by Spike Jones
I also go along with the previous recommendations of:
King Crimson
Flaming Lips
Primus
XTC
and
Mike Patton’s stuff
For a sort of laid back complexity, I’d recommend The Appleseed Cast. Mare Vitalis is a more accessible melodic rock album. Low Level Owl is a two volume masterpiece, that has earned them comparisons to Radiohead. On LLO almost every other track is solely instrumental, and the entire two album set meanders like a single, slightly hypnotic, piece of music. I’d recommend giving “Steps and Numbers” and “Rooms and Gardens” a listen to get an idea for what the music is like.
I second the recommendation of Sigur Ros. They are like musical poetry.
Have you tried The Cure, specifically Disintegration? Incredibly layered, intricate, moody stuff, and the lyrics are great. Of course, Robert Smith has the weirdest voice in music that I’ve heard so far… Start with “Fascination Street,” and work your way from there. Rasputina is also good - one singer, three cellos, loads of fun. And I’ll put another vote in for Sigur Ros.
By the way, Wristy, I really like your name.
Check out any of the first 4 albums by Béla Fleck and the Flecktones, particularly UFO TOFU from the album of the same name. I’ve played it backwards on my computer, and though it’s not completely palindromic from beginning to the end, most of the musical themes are played both forwards and backwards. On the same album is The Yee-Haw Factor which has lots of layers to it, and Life Without Elvis with plenty of strange rhythms.
[sub]No banjo jokes, please[/sub]
You might try Wilco’s Yankee Hotel Foxtrot, which is a pretty ambitious album. It’s also very easy to listen to, with lots of beautiful, haunting melodies.
Warren Zevon has done lots of ambitious stuff, in a literary sense. Great music, too.
Beck does lots of complex things. try Odelay.
Once again, I’ve gotten to a thread after everybody has posted what I wanted to say. But I’m going to say it anyway:
The Flaming Lips
Bela Fleck
Tom Waits (anything after Swordfishtrombones for you)
and early Phish
If you find Zappa fun, I would also suggest Ween, although they don’t really fit into your OP.
-tool
spiritualized - Ladies and Gentlemen We are Floating in Space
it originally came in a giant blister pack but where the pills would be were cds, one sone on each.
I’ll third a sigur ros. Their music is simply breathtaking.
as a slight hijack from pulykamell’s post, these guys actually sing “hopelandic”. Never heard of it before? Thats because they made it up themselves. Its extremely bizarre, but it is sang so beautifuly that it makes you feel like you know what he is saying, but when you stop and pay attention, you realise you dont have a single clue whats going on.
I’ll tack on Hooverphonic. I’m suprised nobody has mentioned them yet! They are a Belgish “band” if you will. 4 albums out to date. Hooverphonic isnt like anybody else, so I cant compare them to anyone, nor would it be easy to compare anyone else to them. They are IMO the definition of “complex” (if you dont count electronica.). Everything just screams diverse with them. They dont fit in any genre, but they touch on just about every kind you could come up with. Each album is completely different from the others, and to tell you the truth, you’d be hard pressed to recognise that they are done by the same people. So I’ll give the lowdown of each album.
"A Stereophonic Sound Spectacular"
-First album out around 1998. The music sounds highly influenced by 80’s music, so its chock full of synth, but not enough to be even remotely called electronica. Its got a Space/Trip Hop feel to it almost. The lyrics dont make hardly any sence, and sound clips and famous riffs are abundant. Theres actually a song called Cinderella that the core music is based around a trucker using CB talk. Very strange, but VERY catchy. I’d recomend this album in a heartbeat. All the songs are by a woman singer named Lesje or something strange like that. Either way, its gorgeous music.
"Blue Wonder Power Milk"
-Came out a few years later. Totally different sound this time around. The sound clips were taken out and the male band players join in on 3 of the songs. Oh, and the Lesje woman dropped out and Geike joined. The first song on the track “Battersea” shows off her amazing voice with this haunting ballad. The guys songs have a gritty feel to them, but are soothing at the same time. Still lots of synth. Lots of orchestra.
"The Magnificent Tree"
I love this album just because they have a song with the guitar riffs from “Guinnevere” from Crosby Stills Nash and Young. This is probobly the least liked by Hooverphonic fans because it is so dramaticly different than the previous album. Its very…very…popish. Well some of the songs atleast. Their strangeness still comes up with songs like “Autoharp” (which like Cinderella, is based off of a instructional video for playing an autoharp that the band came across…so what do they do? Sing a song about how somebody is like one!) The guys are out of singing for good, minus a spotlight part in “Frosted Flake Wood” where one of the guys sings the part of a mushroom who is trying to sell himself to a kid…um, the song is very VERY strange to say the least, thus it is my least liked. It goes on and talks about Big Bird 
(heeeelllllllloooo?!) saying no to drugs and such. Dont buy this album first, I warn you. While it does have some amazing songs on it (very soothing and upbeat alike), you will be turned off from the band right away. It took me a good 7 times listening all the way though to finally learn to apprecaite it. Now I love it. Once again, lot of orchestra with band. Nice contrast.
Jackie Cane
This CD is an even further cry from the rest of albums. You can tell its an evolution, but this time around, they added in a 50’s swing feel, and several new slow songs. HPH (Hooverphonic) took one song from the previous CD (the song Jackie Cane from TMT- about a woman who was too kind for her own good, so she was taken advantage of by everyone and had a tragic death as a result) and made an entire album about this fictional character. Some critics think its actually about Jackie Kennedy, and while it very well could be, I think its a stretch. The album starts off energetic with lots of hope (Jackies foray into stardom), then leads up to “The World is Mine” (where DUH! The world is hers. she’s cool. popular), then on to creepy synth sounding stuff for her world starting to crumble, and finally slow sad music for her final fall. Lastly, it ends on a high note for how “Death isnt the end”. Its totally unique how its dedicated to a fictional characters life, and thus, the album as a whole follows life with its sound.
You have to listen to all of one album at once to truely get the music. HPH claims that their albums are “like a solar system. Each track or planet is very unique, but you have to see it as a whole to truely appreciate each and every detail”. I agree. You want complex, go with Hooverphonic.
I’ll give it a shot…:
Einsturzende Neubauten- tons of layers, unorthodox instruments, gutteral german vocals…what more do you want? A good album to start out with is Haus Der Luge
Angels of Light-ex Swans frontman Michael Gira’s folk masterpiece…again tons of layers and waves of sound along with acoustic instrumentation.
Sparklehorse - beautiful like a rotting rose is the best description I’ve heard. Linkous produces all tracks with vintage equipment, with lots of interesting atmospherics, static, etc.
The The - Does some interesting stuff. I really like Dusk and Naked Self though others might recommend other albums.
Pavement - might have some of what you’re looking for. Try Slanted and Enchanted
Sixteen Horsepower - I’m not too familiar with them, but Folklore has a certain ambience and is definitely a change of pace from most of what’s out right now. Think O’Brother, Where Art Thou? on downers.