You might consider Napster's new $15/month unlimited music rental program if that model is compatible.
They also sell tracks in 128 kbps protected WMA format, quality is pretty good though nothing like the lossless FLAC I use to rip my own CDs, or even the LAME -alt-preset-extreme I use for my Zen Xtra.
128 kbps WMA is also what everyone else except apple sells, though I thought I say that buy.com's buymusic.com offers 192 kbps on at least some songs.