If you haven't see Last.fm yet, you should check it out. You can listen to streaming music basically for free. If you put in the name of musicians you like, it will play things that it thinks are similar based on what other people listen to. It's how I recently found Rammstein. (Whom I highly recommend by the way.)
Best thing about Last.fm is that it works in Linux. In fact Amarok even integrates with it. (I also highly recommend Amarok by the way. If only for the auto-fetching of song lyrics!) Or you can use Last.fm's own weird web-based player, which works fine in Linux too.