Criticism: INTERLACING? WTFX? How do you take a non-interlaced source and make it interlaced?
You don't have to do a 720p video like Relly said. If you can use a lower resolution, and bump the quality up to equal out the same file size. I'd rather have a lower resolution, high-quality video than a high resolution, low-quality video.
I use H.264 for a video codec and AC3 for audio. I use Matroska as the container.
If you have mencoder, mp4box and mkv tools installed, then these are good commands to use for a very high quality video.
Audio:
mencoder -of rawaudio -oac lavc -lavcopts acodec=ac3:abitrate=384 -ovc frameno -o audio.ac3 c:\video\input\file.avi
Video:
mencoder -nosound -ovc x264 -x264encopts threads=2:crf=15.0:ssim:me=umh:8x8dct:nofast_pskip :frameref=6:subq=7:mixed_refs:trellis=2:qblur=0:bf rames=16:b_pyramid

artitions=all:weight_b:qp_min= 0 -vf scale=1280:720,harddup -ofps 30.000 -of rawvideo -o video.264 c:\video\input\file.avi
(You can also substitute crf=15.0 for bitrate=2000 [or whatever you want]).
Muxing it all together:
mp4box -add video.264 -fps 30.000 video.mp4
mkvmerge video.mp4 -D audio.ac3 -o "MYNEWGAMEVIDEO.mkv"
You'll now have the highest possible quality video. This will produce video quality that's better than professional movie studios (this still depends on target file size).
Update:
I'll record a short clip to show off the quality later.