I've been using Real Rhapsody for the past week or so. I hate real player with a passion and was very skeptical at first but I like it.

Combined with MusicPlasma (thanks ninti), I've found 10 new bands that I wouldn't have tried otherwise and probably 10 more one hit wonders that are catchy enough to listen to but I can live without their CD.

I thought their business model was a little weird but this might work.