If you get one with solid state memory (as opposed to a little hard disk or a CD-drive), you'll need to figure out the optimum in terms of encoding quality (read: what you think sounds good) versus file size. This is a very personal issue, and the only advice I can give you is to experiment and listen a lot with various encoder settings. That said, I would go for a device which can store about 4 CDs of music or more. That'll keep you from getting bored (and frustrated with uploading new music all the time) too soon. Most devices have a FM radio tuner too: a useful addition.
As for the age-old MP3/WMA/Ogg Vorbis-discussion: let your ears do the talking. My player (an iRiver MP-190) unfortunately cannot handle Ogg Vorbis due to rather arcane hardware restrictions, otherwise I'd probably be able to fit 4 *CDs* rather than 4 *hours* worth of music in its memory at the quality I want. (Newer iRivers can do Ogg Vorbis, by the way.) That said, after MP3-encoding my collection of 200+ CDs I'm not going to go through that again.
Oh, another thing to watch out for is battery life. I get about 12 to 13 hours worth of music out of a single rechargable NiMH-battery (AA, 1600 mAh) which I think is pretty good. Some devices have a built-in battery which charges itself through the USB port: while an elegant solution, I prefer classical batteries as you are not always within reach of a USB port.
Don't expect the sound quality of the little players to match your top-of-the-line stereo installation; on the other hand, don't expect it to be abysmal too. I was surprised to find out that I can almost as easily distinguish between good and bad encodings on my stereo as well as my player; in fact, I had counted on the fact of me not being able to hear all the nasty artefacts introduced by a lower quality (and thus space saving) encoding. I was very wrong indeed :-P.
Hope you found this useful, and let us know what you bought!
