Emma Bull! I got her autograph recently, and nearly plotzed I was so excited. She was funny and kind and wonderful, exactly what you'd hope.
For the more adventurous, I'd recommend China Mieville, especially his first novel, King Rat. His language is dense, even demanding, but the concepts are well worth the effort of unpacking. Going a bit further out there, he's also written stuff set in the alternate world of Bas-Lang, starting with Perdido Street Station.
In the same vein as Mieville's more out-there stuff, there's the Aussie writer K.J. Bishop. She's only got one novel out at present, the fantastic and haunting Etched City, which is a sort of alternate world urban fantasy, more akin to Michael Moorcock's Elric books than, say, Charles de Lint. It was nominated for a World Fantasy award, and you can immediately see why. Heaping helpings of existential despair for everyone!
Not to knock de Lint. Memory and Dream is one of my favorite books of all time.
I might also suggest Elizabeth Hand, particularly her brilliant Waking The Moon. It made me sad, and it made me angry, and it made me rethink the power of scent as a writing tool.