I few days ago I mentioned Songza, which I was, and am very taken with. However, there is a bunch of other similar engines out there, so I thought I'd take a quick look. I did several searches for different artists, unusual tracks and so on. All very unscientific, but if you want more than that, well - feel free to experiment yourself and post the results! :)
Streampad was pants. Couldn't find anything that I was interested in.
Songerize was little better. You need to know track name and artist name to search. If you just put in an artists name it finds what it finds and just plays it without reference back to you. Oh, and the favicon was almost exactly the same as Songza.
Streamzy wasn't at all bad. Found half a dozen Wakeman tunes, located 'Mouldy Old Dough' (which Songza couldn't find), but failed when it came to Michael Nyman. Didn't really like the interface a lot though.
Deezer had a sophisticated interface, slick and attractive, allowing you to save, share playlists and so on. Unfortunately it didn't have any of the artists or tracks I was interested in.
Pandora is still out there of course, but since I'm not in the US I can't use it.
Musicovery is an interesting variant in that you define the type of music you want to listen to - vocal pop, blues, soundtrack etc, then the mood - dark, calm, positive and so on, and it produces examples for you to listen to.
Dizzler had a nice interface, but a limited number of songs; at least of the stuff that I was interested in!