I got one of the $17.50 mp3 players from surpluscomputers.com, shipping included. It runs on 1AAA and doesn't have many features but its audio is pretty good and you can't beat the price. That's with zero memory. You add an SD card. I've seen 128MB cards for as little as $20 and you can also use it in your digicam (depending on model), etc. I have a 256mb card in a PDA that I don't use so I'll put it in the mp3 player. Right now I have a 32mb card in it that was $5.99 from Rite Aid.
Frontier Lab has a fancier 1AAA player that runs for about 13 hours and uses an SD card but I haven't tried it yet. Their old model, which used two AA's and a CF card, was a nerd favorite though it's a bit out of date these days. I still might buy one since I have several CF cards including a 4GB card, from digicams and other devices. Ebay is the best place since if you buy direct they ship from Hong Kong and charge huge shipping fees.
I refuse to use anything with DRM. I'm happy to buy players with no AAC. I don' t care what formats the online vendors offer. If they don't have non-DRM formats I won't buy from them. I can always rip my own CD's to mp3 or whatever else. Yes there are patents on MP3 but whether those patents are legally valid is a separate question. Suffice it to say that there's plenty of MP3 source code you can download, and the patents even if valid are due to expire in a few years.
I personally would not buy a player that doesn't have easily replaceable batteries (rules out all the ipods) and doesn't either have a large internal hard drive or easily removable/upgradeable memory (rules out a lot of players with internal flash). However, if you don't mind non-upgradeable memory, iRiver has some nice players, that even play Ogg Vorbis, which is a true free format (no patents).
Finally, my favorite source of music:
www.magnatune.com --- check it out, they are great, mostly artists you haven't heard of but just about all of them are good. All free to download and no DRM anywhere.