I have a Zen Stone Plus (2 gig). Same as the Stone, but it has a little screen so you can see what song and other info. Go for a Stone or Stone Plus.
I bought my wife a 2nd gen Shuffle, and the Stone Plus stomps it. plus, I just had to have Apple replace her Shuffle because it died in a month.