Do not listen to these people, they have clearly never tried to actually convert videos ( NOT DVD's) and gotten decent results
The best program to convert videos also happens to be
FREEIt's called Super
http://www.erightsoft.com/SUPER.html
It can convert pretty much ANYTHING to the correct mp4 output
The maximum resolution that the ipod can push out are
640 X 480 good for video out ( will display at a lower rate on iPhone)
640 X 360 good for 16:9 video out
If you are just running it on your iPhone display I would recommend
480:270 for 16:9
480:320 for everything else ( will probably be stretched )
make sure that your video bitrate is below 1500 kbps ( so choose 1488)
Audio should be set to 48000 , 2 channel and 160 kbps
those are the settings I use but you can lower them if you want to make a smaller file
also not all videos are high quality. if you want to see what the exact specs of your video download VLC player and media player classic to figure out what the framerate,bitrate, soundrate, etc are for the video
that way you don't reencode it at a "higher level" ( thus making it bigger than it should be)
however if you are a person that is not that technical, then I would recommend Videora
http://www.videora.com/en-us/Converter/iPhone-3G/
way less options but it seems to encode faster than super ( but quality is lower than a "well selected" encode"
