Encoding times depend almost entirely on the speed of the cpu.
Of course, some encoders are faster than others, but the faster ones are not free. If you want to get one that would work with DVDRebuilder, CCE Basic would be the most economical choice. I advise using the HC encoder first, just to see if you can tell the difference between Rebuilder and Shrink, especially if you use a big screen tv.
I have just built a new computer with a Core 2 Duo cpu, got it running at 2.7ghz. I haven't reencoded a dvd with it, but did convert a 700mb avi to dvd last night. It took 2hrs to reencode with ProCoder using the slowest and highest quality settings . That would have taken about 3-3 1/2 hrs on my old AMD 64 3000+. Intel cpus are slightly faster for video encoding, and the new Core2 Duos are very, very good for this particular task.
On the old rig, I would let it work overnight to reencode a dvd. It never took more than ~4hrs as I recall. But again, I was using a faster encoder than HC, and a pretty good machine. With the new machine I believe I could do batch jobs of two or three dvds overnight. We'll see. I haven't bought any new dvds lately to try it out.
So, to sum it up, try the free version of Rebuilder. Use the HC encoder and let it run overnight while you sleep. You'll never know how long it takes with your particular machine till you try it. If you don't find the quality is better, or not enough to go to this much trouble, you can always go back to Shrink.