On my jailbroken iPhone 4, I use Grooveshark exclusively. Granted, that doesn't do me any good elsewhere since every app store/marketplace has rejected GS for obvious legal reasons.
On my Focus, I use the integrated zune. It took a while to get a hang of the desktop software, library organization and such, but eventually I got it tweaked to my taste. The zune marketplace has a great feature that I haven't seen anywhere else; it lets you pick your payment method before the purchase. Without manipulation to an apple id (for example) prior to even initiating the purchase, the bill goes to wherever the default is. But with Zune, I can click buy, then click payment method, and select from my credit card, ATT market, or my debit. Depending on my financial status, or whether or not I've paid ATT for the month and don't want to deal with the inconvenience..etc, I can choose how to pay on the spot, without the bother of leaving the marketplace to change an account's default payment method.