The Rio Carbon is excellent, but no longer in production. You can get a refurb at amazon very cheaply. It is tiny, and self-databases, so you can just drag music on and it will build the id3 tags itself, no need for any software anywhere. Wish more players had this option.
The direction of most players these days is 1) tiniest possible and 2) video; I don't need either, I keep waiting for good high-capacity ipod competitors that aren't proprietary but nothing yet.