There are different types of player.
I prefer Flash players, basically USB-sticks. They are very small and have little weight. Carrying an iPod around or anything bigger than an iPod mini all the time is quite cumbersome. There are some alternatives like iRiver's H-120 or Creative's Xen Touch, but both are as large an bulky. They offer up to 60 GB of data however.
There are some microdrive players like Creative's Muvo². 1,5 - 4 GB.
I would go for a MP3-Player with 256, 512 or 1024 MB.
50, 100, 200 songs usually, even more in .ogg or .wma.
You should make sure that your MP3-player has an output power of 7 mW left/right at the minimum. 14 mW is usually 7 mW x 2. I personally recommend nothing below 2x 10 mW, not powerful enough.
You should also read tests about battery life. 8 hours is the minimum, I would go for 12-16 hours, personally I would say even more. Usually MP3-Players use AAA batteries, some AA like iRivers iFP-series. Others have fixed rechargeable cells, but I would go for AA/AAA devices. You can replace and change them on the fly if need arises, the others usually need to be at the USB port to charge.
FM-Radio should be included, most MP3-players have also voice recording, but it is the feature I use usually not at all. Some players can encode directly to MP3.
Many modern players need a cable to connect to the computer - some are directly plugged into the USB, better if you need this as a thumb drive. USB 2.0 is a good idea if you want to use it as a thumb drive, too, in this case I would recommend:
Creative MuVo TX FM, 256 or 512 MB.
I was quite fond of the iFP-799 of iRiver, but it is too large and bulky. However, it had impressive battery life and great 18 mW / 18 mW output power.
Right now I am using this one:
http://www.weyco.de/html/weyco-5star.html
It might have another name in the UK, it is just an import from Korea.
Great output power and lots of features, good quality overall. The big problem is that it has only 7-8 hours battery life... like those crappy iPods.
http://www.weyco.de/html/produkte.html
if you compare to
www.iriver.com, you can see they are trying hard to copy their stuff, hehe...
Get some quality earphones. Except iRiver's, who use Sennheiser earphones, most are sold with rather shabby ones. If you want it cheap and good, get Sennheiser MX300/400/500.
Sony's EX51/EX71 are good inEar-phones, I used the ED21-LP for a while, great grip, but the MX300 sounded just better. Right now I use Sony EX51LP.
Bottom Line:
iRivers have quality sound, superb output power and battery life.
They are however too large and weigh much more than the average.
Creative MuVo TX FM are great devices, except for the mediocre 7 mW output power...
As there are many MP3-players out there, just make sure to check output power, if the device needs a manager soft or can be used directly over USB, and battery life. (Expect the truth to be 75% of what they say <g>)