A few different things....I apologize if you already know any of these:
Mr. Bungle: Pretty well known avant-garde band, featuring the famed Mike Patton on vocals.
I recommend the album 'Disco Volante' for your Avant-Garde Jazz needs. Very jazzy, very weird at times, and produced by John Zorn. ^_^ Another of their albums, 'California,' also good avant-garde, but much more accessible. They tackle the different musical styles of California, from songs echoing The Beach Boys to........<_< other famous "California" sounding bands.
It's one of my all-time favorite albums, and I've had it for over a year. This will also satisfy your need for clean vocals. Disco Volante has vocals of course, but this has even more of a vocal focus. Very catchy, very fun, but also very musically satisfying.
Fantomas - This is Mike Patton's current main project. Unlike Mr. Bungle, everything in Fantomas is written by Mike Patton. If you've ever heard John Zorn's Naked City, this is very much influenced by that. If you know John Zorn, you'll find they have a lot of the same "tricks" that John Zorn uses (flash-card compositions, cartoon music, movie theme covers, noisy segments, etc.), but they definitely have their own sound. Their most accessible is 'The Director's Cut,' which is filled with covers of movie themes ala Fantomas. Besides that, I recommend 'Suspended Animation' and 'Delirium Cordia' (flash-card composition ala Zorn).
Secret Chiefs 3: This is the current main project of former Mr. Bungle and Faith No More guitarist Trey Spruance. I recommend 'Book Of Horizons,' their most recent album. The idea here is that Trey has created several different "bands," and they each have 2-4 songs on the album, in completely different styles. A few are.....classical sounding compositions, soundtracky music, death metal, indian music......it's interesting.
I'll post some more later. ^_^