I'll recommend Tori Amos' "Blood roses" too. I'm not a fan of her, although she's very talented. As far as I remember there's also another good song on "Boys for Pele" (which is the record "Blood roses" is from), but I can't remember the name of it. I think it's the one before "Blood roses". I just borrowed the cd once. "Cornflake girl" is also an okay song, although it is kind of synthetic. She has also done a version of Gershwin's super fantastic "Summertime" (all-time favorite composition). I don't know if this is on an album, as I have it as mp3, but it has crowd noise, so it's probably from a concert. It's not the best version I've heard of the song, but it's really hard to make a bad version of this fantastic song!
I don't really like Nick Cave, but I have "Where the wild roses grow" on 7" and it's a good song. The other stuff I've heard from him (which is not much) was either mediocre or crappy. Hey, didn't he start out making punk? Talk about selling out!