I like this little iRiver 256M flash player. Small and light and great for running. Not very hackable though. The latest firmware does let you manage it like normal removable flash storage so you can use it easily from Linux or on Windows without any special software. TechTV Review Firmware upgrade info
The Archos harddrive players are getting a bit dated, but that also means they are cheap. I picked up a 10G Studio player for $85 a while back. It only has USB1.1 and a tiny 2-line display which makes it nearly impossible to navigate your songs, but I just stick it on random and let it do its thing. The best part about it is that it is very hackable. Check out the open source RockBox firmware for it:
[Update March 10, 2004] The Archos hard drive won't spin up anymore. Guess it took a few too many beatings coming with me on all my runs. Waiting to see if anything interesting comes out soon to replace it.