I'd also keep an eye on eMusic. It's more geared towards downloads, but they offer a lot of really great editorial content for discovery plus they offer multiple streaming radio stations for members. They've got smart people so I think they might make a surge in features.
A lot of people are into MOG.com as well. I have issues with their CEOs attitude towards licenses and how the money goes to creators, but otherwise the catalog is strong and they offer solid access across multiple platforms.