Late, but depends on your needs?  Since you said MP3 or MP4 (they typically refer to audio only or video+audio)  Do you need video playing capabilities? (IMO, PSP is still one of the best video players)

Cheap Chinese players, IMO, aren't that bad.  I had one (which I bricked cause I was stupid at the time).  THe interface is a little clunky and takes a little while to respond, but IMO, a slightly harder to learn interface is a small price to pay - you get used to it after a while.  Responsiveness isn't terribly big an issue unless you're trying to browse through a large collection of music.  The player came with radio+mic as well.
Again, really depends on your needs I guess.