michaelk: Thanks for the hint, I'll remember to get a player that has a clip or loop of some sort to keep it in place.
I'm still not quite sure which mp3 player I should buy, but this list has narrowed the options down a bit, because I have a lot of files in the FLAC format:
http://en.wikipedia.org/wiki/FLAC#Hardware_support
I just discovered that you can even run a variety of Linux (Rockbox) on a couple of players, so that might be another thing worth considering when choosing a player.
On a side note: Linux was the only reason why I bought a Linksys WRT54GL wireless router and almost everyone I asked on IRC channels, forums, etc, told me to get one of those (apparently not just because Linksys was supporting Linux, but also because their routers are good).
So I'm surprised that there's no standard player that Linux users swear by. Or isn't Rockbox useful enough to be an argument for exclusion (of most players)?