The Zen, definitely.
For £20.00 you get mp3/wma playback, FM Tuner and voice recording. And it runs for 14 hours on one AAA battery. Get a set of four rechargeable AAA cells and a charger and you're in business.
Mp3 files are better quality than wma and with that in mind you'll only get a little over a hundred songs on 512Mb of memory. Unless you're a Napalm Death fan of course, in which case you'll get about 500 songs on it
That may seem like a lot of songs but you'll soon get fed up with such a small storage capacity and be looking to sell your Zen and upgrade. Maybe.
I'd recommend about 4Gb storage capacity to start.