For Linux I've heard that specific support isn't really necessary beyond it showing up as a USB drive, however the Linux category on the wikipedia comparison page must be referring to something. I've also heard advice like getting an iPod + Rockbox, however there are possible downsides with putting on a 3rd party OS (ie warranty issues, a UI not quite made for the hardware), as well I'd much rather support a company who supports ogg and Linux out of the box. One popular choice for ogg/Linux seems to be iRiver, however I don't know if this is the only choice and this page seems to suggest it's Linux and ogg support isn't that great after all.
As well there's also the criteria of durability, sound quality (do the different players have differences that people besides audiophiles would care about?), size, and cost.
I know slashdot has covered this subject in the past but I'm sure things have changed since 2002.