All of my mp3 players with a radio have a record function, so it's quite easy to record the radio directly to a wav file. I also have some of my devices modded with
www.rockbox.org firmware, which also allows recording the radio with a variety of formats or quality. I find the quality no different than live radio. Your cellphone might also be able to do this. The chips used for radio in small devices are pretty high quality, so I'm guessing that the sound is as good as a good old analog tuner.
Here's another problem though, what's a device that can record files with RDS song information? All my local radio stations identify the current genre and song title playing, which I can see with an RDS equippped radio, but that device doesn't record the info. I suppose there's some usb stick tuner for PC which would do this.