I use a program called Procoder for avi to mpeg2 conversion, then
DVDLab Pro to put it into dvd format with menus. Combined, that is about $750 worth of software, so you may not want to follow my lead on this.
A lower cost alternative that uses a good encoding engine would be something like TMPGenc Author 3.
And there are some free programs that use good encoders as well. FAVC is one, and if you use the HC encoder that is included, you will have excellent results.
http://favcfavc.googlepages.com/ Make sure to install AviSynth and Net 2.0 (if you don't already have it). There are links on that page for those two necessary items, and both are free.
Encoding times depends primarily on the speed of your cpu. Dual core cpus can speed this process up if the encoding programs are set up to utilize both cores.
I normally use ImgBurn to do the actual burns to disk. It is a free program, and I highly recommend it. If you are not familiar with it, look through the guides at the ImgBurn forum.