I really wouldn't like watching videos on anything smaller than a psp though... and even then, the only reason why I would watch movies on a psp is because you can slow down or speed up the video... 0.5-2.0X speed. It is quite nice when watching action movies or just stunt videos of bmx bikes or xgames or something.
I use videora for all of my iphone/PS3 video conversions; the advanced options are as good as paid software. To use normal mode you have to be connected to the internet so it can show ads in the program, but if you use power mode, the program can run without an internet connection to download ads. So I'd recommend blocking the program through the firewall and then the program will run faster.
MediaCoder does everything... and it is free
It comes with UI Plugins for different devices,
which make transcoding very simple.
It has advanced features like cropping and video filtering (which is particularly good at removing artifacts from analogue tv recordings).
You might be suprised how pleasant watching on a small screen can be. 320x240 may not sound great but the reality is that 240p and 480i are essentially equal.
Granted, you can't fully appreciate UFC action on a 3' screen but its great for watching The Office, or American Idol.
Furthermore, the OLED screen on my Walkman is easily 3-5x better than my laptop display outside in the sunlight.