I love my Sansa Fuze (as recommended by AnythingButIpod – link above). I got the 8gb one and have a further 8gb microSD card in it which seamlessly integrates with the player, which is unusual I believe.
The sound quality is excellent (for an MP3 player) the only drawback with the original firmware is the rather clunky equaliser – which I didn't use given the quality of the 'normal' settings anyway – and the playlist support is difficult.
I have recently rockboxed it (Rockbox is a shareware firmware that replaces the firmware on a number of players. Link thing: http://www.rockbox.org/). This has enabled a much better approach to creating playlists and customising the sound, the problem is the sheer number of settings and things to fiddle with is baffling in the extreme, however it offers a 'proper' oldskool treble and bass adjustment which I can use. It also does other geeky things like enable game playing (including Doom I believe!) but I just can't be bothered with this side of things.