My sister recently purchased a Samsung YP-30SH.  It's really nice.
For about $180 retail or $140ish Ebay you get a 128 meg mp3 player with arm, neck, and belt strap (great for working out, which i use my compaq ipaq pa-2 for).  I've never had it skip or even feel that it was coming loose, and i run some rough trails and have even jumped with it.
It records voice too (never used it, just a nifty thing) and has a decent file transfer system that is fairly fast.  Runs on 1 AAA battery for about 6ish hours, which is really cheap.
Only downside is that you can't expand the memory and the included ear buds aren't that great.  128 megs will get you 30 to 40 songs though, which is plenty.
It is tiny too, you'll be amazed how small and light weight it is.  Great for working out.  The whole thing just looks and feels damn cool too.
If you want cheap, i use a compaq pa-2.  Comes with 64 megs of MMC flash but is expandable easily.  About pager size, slow file transfers, decent file transfer software.   Comes with a belt clip that is super sturdy.  I only reccomend this if you want a cheap solution.  Ebay offers them for less than $100.