I just purchased a Creative Labs MuVo V100 2GB and so far I'm happy with it. My criteria (and a lot of why I avoided the IPods):
1) No cable, proprietary or otherwise; stick it directly into the USB port. It even doubles as a stick-drive if I ever need it and cost less than I paid for my 1GB stick only a year ago).
2) AAA battery. No expensive "proprietary" lithium battery to replace; can get it cheap anywhere and with rechargables, I'm good for the long haul. No "unremovable" battery here.
3) No "copy-protected" or "proprietary" special format like ITunes or any nonsense like that. Just give me an MP3 player and leave it at that. If I ever do replace the player with another in the future, my whole library will still be valid for as long as MP3 remains a viable format.
4) Simplicity. No ITunes. No Windows Media Player. No Playlists. Just stick it in, copy files via Windows Explorer, do the "Safely Remove Hardware" and you're ready to go.
The unit has its limitations; no screen menu, no radio etc. If you're a fan of playlists or such, then this might not be for you since there really isn't much of any software to "manage" your files. Basically, plug it into your computer and it shows up as a hard-drive (folders and all), copy the MP3 files over, then you're done. It plays the tunes in file-name order and that's that (though I think there is a shuffle setting). For me, I take this to the gym and pretty much that's it, so that's what I needed it for.