Grab Handbrake (Windows, Mac, Unix)
For zero effort just use the iPhone preset in the GUI.
If you use the command-line, this creates very nice video indeed (via NexusOneForum) that makes use of the h264 graphics accelerator in the phone.
HandBrakeCLI -i "infile.avi" -o "outfile.mp4" -f mp4 -e x264 -q 0.60 –loose-anamorphic -x level=30:cabac=0:ref=2:mixed-refs:analyse=all:me=umh:no-fast-pskip=1 –deblock -E faac -B 128 -R 48 -6 d
Note that it can now also convert unencrypted DVDs directly too.