Well, sicne you're pretty open Minded, we're going to go head on into the AVANT GARDE. Now, you're going to have to really struggle to get into these guys, but once you do, it's totally worth it, and opens you to a whole new spectrum of music.
The Residents - These guys are seriously one of my favorites. They've been going on for a good 30 years or so, and while it not being super inacessible, it's still fairly odd. Some of their stuff is hit and miss, but you can't go wrong with ANYTHING they did pre-1980. I'd reccomend picking up their latest album though, Animal Lover, first.
Frank Zappa - This guy is probably the most acessible of all the people I'm going to mention; Some of his stuff is just really awesome, odd rock and roll. But when he actually gets into super experimental mode, It's amazing. Easily the one artist I love more than any other person EVER.
Captain Beefheart - Basically, Frank Zappa if he did drugs while playing prog blues. So awesome. If you can get ahold of it, Trout Mask Replica is the best of his albums, and generally stay away from Bluejeans and Moonbeams and the other one, Satisfaction Guarenteed I think. They're kinda boring.
John Zorn/Naked City - This guy is crazy. Naked City is one of his many projects, and it goes from Jazz to grindcore to babbling in seconds. Totally amazing. Also does alot of stuff with Patton.
Mr. BUngle/various Mike Patton side projects - Mastermind behind Mr. Bungle and so many side projects that it's impossible to count. To start off, get Bungle's California; Easily the easiest to listen to.
Crotchduster - Avant Garde Joke Metal. Big Fat Box of Shit is one of the funniest, best albums ever. Just go get it, seriously.
There's a good start.