Decide whether you want a CD-based player (iRiver slimx, Rio volt sp250 $100-$150), a hard-drive based (iPod, Rio, Nomad, Archos $200-350), or flash-based (iRock, MPIO, Samsung, $100-200 +extra flash card if wanted).
I wanted flash and finally ordered the Samsung Yepp YP-700H with 128 MB for $200 from Amazon. The 64 MB iRock goes for $100 at buy.com and Radio Shack, add another 128 MB for about $50.