My wife's got a Rio sport 256mb it's nice and rugged and is upgradable. I did a bunch of reviews before I bought it (cuz I use it from time to time mountain biking) and it was about the only one that seemed to be able to handle bumps and jars and didn't have people bitching about buttons wearing out.
Comments
http://www.apple.com/ipodshuffle/
it's really about all i need
http://www.newegg.com/app/viewproductdesc.asp?description=55-102-170&DEPA=1
The sound is pretty good and it has good battery life (I found about 13-15 hrs) on a single AAA.
I don't like the headphones for it though so I use some other ones I have FYI.