Why bother with an mp3 player, get an mp4 player, as most support mp3.
I got this a few weeks ago and I've been very impressed
http://www.microdirect.co.uk/(14724)SumVision-YUMI-Pro-2GB-MP4-Player-Silver.aspx
Ok, it's not quite as well made as an Ipod, but then it's a lot cheaper in price. Has a nice little TFT screen and rechargeable battery so no messing around buying new batteries.
Another option I was considering was buying a refurbished Ipod mini from that site for £70, but decided to save my money, and my sanity from not having iTunes installed on my machine.