If you want MP3s, you pretty much have two options: eMusic & Bleep (the online store for British label Warp Records.) Now, both of those stores (obviously Bleep especially) have compartively tiny catalogs, but if they have what you want, you can download a cheap, high quality MP3, that works on any device on the world, and that you won't have to use any tricks on to make it do what you want.
Napster and the like (Yahoo, Rhapsody, Urge) are primarily subscription based services. You get access to all the songs and can listen to them on X number of computers and compatible devices only. They don't work with the iPod. Think of them almost like on-demand satellite radio--when you stop subscribing, all your downloaded songs stop working. You will have to download their special software to download the songs (although the songs, once downloaded, can be played in WinAmp, Windows Media Player, and most modern music players--but only on X number of computers.) These services also offer purchase-by-the-track options which allow you to burn the song.
The third alternative is the Russian grey-market--sites like allofmp3.com. They're legal in Russia, but the RIAA is making enough of a stink about them here in the US that most major credit card companies won't let you charge anything to them (just like they do with the big online gambling sites.) Funding your account is not 1-2-3 easy.
Making a recommendation is hard--personally, I subscribe to Yahoo Music, and love it. It's got almost everything (although, like all its competitors, there are gaps--some artists and labels just don't want their music online no matter how much DRM you slap on it), and it's dirt cheap. That said, if I unsubscribe from Yahoo, my music is all gone. If you want to keep your music, it's not the way to go, but I've found the subscription fee is a *lot* lower than what I used to spend on CD's, so financially it was the best decision for me.
If you've got an iPod or see yourself buying one in the future, I wouldn't recommend anything but the iPod store. It just works.
Really though, if you want to keep your music and never have to worry about incompatibility, just keep buying CDs and use iTunes or something similar (EAC+LAME here, but that's not for everyone) to rip them to your harddrive.