I almost agree with
fo3nix about the Sony stuff. I've never had any of my Sony stuff go wrong, the quality's been excellent. However I wholeheartedly agree about their poor implementation of proprietary formats. Even though I had all my stuff in Sony atrac format for my old minidisc player, I preferred to rip it all again to MP3 when I got a new player rather than face having to use their rubbish software for the next few years!
I also agree about Creative players and would add that
iRiver H10 20GB would be worth a look.