I got a DAH1000X (256) from MP3players.com. They have a big range of models other than those from the big names. Often worth looking at other models for something different.
I'd look for one that takes AAA batteries rather than a built in battery so it's easy to swop rather then looking for a charging point.
Get one with a radio, handy when batteries are going down.
Look at the format options. I wanted one that would play ASF files and MP3s. I've been told that Ogg Vorbis (OGG) encoded tracks sound very good so that might be one to look out for.