Puedes hacer esto último que te recomienda Robi, pero si no tienes mucha gana de andar configurando cosas, hazte con el Auto Gordian Knot y asunto resuelto... Le configuras cuatro cosas y él se encarga de todo. Por ejemplo, le puedes configurar la anchura máxima del vídeo, ahí le pones los 720, y el programa ya calcula cuál debe ser la altura para que no pierda la proporción.
Este manual te puede servir, está orientado a pasar DVD a AVI, pero también funciona para pasar AVI a AVI, como en este caso:
www.mundodivx.com/dvdavi/autogk.php
Un saludo