I agree with the flash memory-based player suggestion.
I have an iRiver iFP-190T (older model) 128MB. $80 after rebate. I also spent $20 on the armband strap. It also has a FM Tuner and Voice Recorder. Very light, no moving parts to worry about. Perfect for running. The armband does get kind of tight when I'm weightlifting though.
Before I got the armband, I tucked it inside my shirt and sweated on it, so it's at least somewhat water resistant. And of course, check the Hot Deals forum for good deals.