Every time I see reviews of the tiny (both in size and storage) players, nothing has really ever bested the Rio 500, including Sonic Blue's attempts after it. It works well, battery life is awesome, and it uses standard Smart Media for memory, so expansion is also cheep and easy.

Avoid anything without a standard memory interface, and keep in mind Compact Flash and Smart Media will be cheeper since it's been around longer, and isn't as hard to make.