Rhapsody. She can buy individual tracks to own but there’s really no reason to do that. 10 bucks a month for unlimited music. Compared against the amount of content you can access it’s essentially free.
It’s mostly streaming but you can buy songs at the standard rates (~$0.99/song, $9.99/album). I don’t actually use it so I can’t speak intelligently about it but I mentioned it as an option because I know it’s popular and people I know seem to be happy with it. That and similar services are worth investigating for you.
I have Rhapsody and have been doing the unlimited for a little over a year now. You can listen to almost all of it (some random stuff is unavailable and it is rather random what is and isn’t available, but 99% seems to be good). You can download it as well for free to your computer so you can play it back when you’re offline and it also will synch up to some MP3 players. The caveat is that it’s all DRM protected so if you download it to your computer (usually WMA format), you can’t burn it without paying for the album (or illegally stripping the DRM).
I’ve been a Napster subscriber for years. There are Android and iPhone apps for it now, for $9.99 a month you can listen to all the music you want from your computer and download to the smartphones as well as stream to them. I have a subscription that’s no longer offered, so I think I can do more stuff than what is offered now, but as long as you have an active web connection with either phone or computer, you have access to the entire library at all times. I think with the smartphone app, you can only download to the phone for offline use, not to a desktop. I have been very happy with the service, and did a happy dance when the iPhone app rolled out. I avoided iTunes as much as possible even with an iPhone, and now I can bypass it completely again except for updates.
I have known people very happy with Rhapsody, too. I would look into both Rhapsody and Napster if you think subscription service as a gift might be the better way to go. I have heard that Apple is looking into a subscription service model. Those services must be taking a large enough chunk for Apple to think they need to do that, too.
If you’re just interested in MP3’s, Napster sells that format, too, but I would just go with Amazon in that case.