To go off on a bit of a tangent. Time was, I would have a moan at the OP about ruling out Apple devices, but the truth is that Apple have/are abandoning their iPod range. Reason being exactly what CFH suggests, in that people are using their phones now. So for those looking for just an mp3 option, there are probably better options out there.
Thing is, I can understand the overlap with devices like the Touch, and maybe the Nano, but it boils my piss the Shuffle is STILL only 2GB, and yet is the same price it has been for 6 years.
So in summary, get a Sony or s Sansa Clip with a memory card.