I recently bought an iRiver H340 on eBay. Cost just over £200, and it's excellent. Has a 40 gb hard drive, a built in mike and also a plug in mike - does fine recordings. It's multiformat so it can handle many file types. Will display jpeg photo files.
I wouldn't buy any mp3 player that doesn't make live recordings - eg iPod.
Ray