I got an iRiver IFP-390T for Christmas, has 256meg flash memory. I use it for ice skating, and I do jumps and spins (and some falls, LOL), so it's getting plenty of movement and jarring, and it's been doing great. It comes with an armband, and it's so light that I barely notice it's there. And it's got great features and the music sounds wonderful. And the controls are easy to use, even through a shirtsleeve...
The stock earbuds are OK, but I've ordered new Sony canalphones since I need to drown out the rink's PA system that plays bad music. The stock ones would probably be fine for jogging, as you don't want total isolation (car horns anyone?), and they do fit in fine (they didn't fall out even in spins). But other people can make additional suggestions for better quality phones.
At any rate, for an athletic use, I highly recommend the iRiver IFP-390T...
Only thing is that it's about $160-200...