I've tried rdio for a couple weeks (free trial), and have been very happy with it so far.