Personally I'd probably go for a Rio S10 or maybe an S30 (which comes with an armband for gym use). Small, light, 35 hours from 1xAA on the S10 (15h from 1xAAA on the S30 which also has a tuner), SD card expandable, nice UI, etc.

Ok, so I'm biased, but you can still find S10's about $66 new and $49 refurb (froogle) which means they're a bit of a bargain.

Hugo