summary - personally, i would go for a portable dvd player - but see below
lots of options - screen size is important for viewing video, 2inch phone screen is too small - 3-4 inch is still a strain - personally, i would consider a portable dvd player - see below
one problem is how to get stuff into an mp4 player, because each player has a slightly different file format - downloads are big, and ripping dvds to portable formats takes a long time. as video files are pretty big, you need to think about this - eg feature films ripped to mp4 files work out about 400Mb or so. - so you will only get 4 or 5 on a 2Gb card.
so - some options
if you want to watch dvds only, then a 7inch portable dvd player will be cheaper and better probably - also handy for in car. if you have a dvd recorder you can record tv shows, or just watch prerecorded dvds
mp4 type options
ipod touch type thing, good 3 inch screen
psp will play movies on umd disks, but will also play movies on memory sticks - although slightly lower resolution. compatability with ps3, which may help
archos - very good, but slightly expensive - lots of attachments, one that lets you record staight off tv - you can also output back to tv, which is useful
larger screen mobile phones will be pretty good also
finally note also that all these players are also excellent mp3 players with album artwork etc etc
we have accumulated all of these over the years. personally, i find 3-4inch screens too small for continued viewing and we just use these for music and games. The portable dvd player gets plenty of use in car journeys/holidays etc