Well, I’ll stick with rock and indie art-rock kinda stuff.
Tortoise - Start with the album Millions Now Living Will Never Die - Fairly low-key music on the whole, but incredibly complex and weaving a wide range of influences, from Krautrock to dub to jazz. One of the essential bands of the 90s, and criminally underappreciated in Chicago, but get due props everywhere else it seems.
Sigur Ros - Agaetis Byrun I’m not even sure how to begin describing this group from Iceland. If you like some of Radiohead’s post OK Computer stuff, you should enjoy these guys. Ethereal, spacy, occassional snips of non-sense Icelandic words. This album blew me away the first time I heard it. Lots of lush strings, keyboards and subtle textures. Gorgeous.
Stereolab - Emperor Tomato Ketchup Ok, now I’m not sure if it fits your definition of complex, as Stereolab tend to take a very minimalist approach to their music. A typical Stereolab song tends to groove on two chords, a pulsing drum beat, and intertwined female vocals, with a decidedly Marxist theme. They’ve picked up where Krautrock bands like NEU! left off. It’s cerebral and arty, yet accessible at the same time.
Can - Tago Mago - A German band from the 70s, I would regard these guys as the most musically interesting and diverse band I have ever come across. You might lop it in the prog-rock category, but I don’t see them as the spiritual kin of bands like ELP, Dream Theater, Jethro Tull, et al… These guys may take a bit to get into, and all their albums are quite different experiences, so if you don’t like one, try another.
Sonic Youth - Daydream Nation is the classic album. If you want something a little poppier, yet rawkin, try Dirty. Lots of guitar noise, lots of off-kilter rhythms, wonderful textures. Daydream Nation is certainly in my list of Top 5 most important rock albums of the 80s. Dirty is often underappreciated by Sonic Youth fans, but a great way to acclimate yourself to their sound if you don’t want to take the great head-first leap into Daydream Nation.
Flaming Lips - The Soft Bulletin or Yoshimi Battles the Pink Robots If you like Radiohead, I think you should be able to get into these guys, as long as you don’t have a problem with lead singer Coyne’s idiosyncratic voice, which some people do. Complex arrangements within the confines of pop structure. To me, they are the American counterpart to Radiohead, and I dare say better on the whole. (Although OK Computer I’d rate higher than either of these two albums…if only slightly.)
So that’s off the top of my head. If you tell us more examples of “complex” music you like, we could fine tune this a bit more.