I'm having issues finding a good MP3 player that can play videos and music. I mainly want the videos because I want to upload all the Elfen Lied episodes on it and then have some room for some music. I don't want to get an Ipod because I don't want to have to download Itunes.

Would I want to buy a MP4 player? Do they all play videos and music?

What do you recommend?