Most of the free converters will not have much better menu creation options than ConvertX, and they will probably not match it for speed. AVStoDVD, set to use Quenc, or a one pass OPV encode with the HCenc encoder would be reasonably fast, but might still lag behind ConvertX. AVStoDVD is the program I recommend most often as an alternative to ConvertX, especially to those just starting this sort of thing since it is free, but its menu creation is definitely a weak point.
You might want to look at the trial of TMPGenc Authoring Works 4. TMPGenc was never known for speed however.
If ConvertX will output as separate audio and video streams, you could convert with it, then build a menu in a pure authoring program. I do this with AVStoDVD whenever I want a fancy menu....I use DVDLab Pro to build the menu.
Hardware is the key to speeding things up the most, especially cpu speed. I was amazed at how fast my quad core is for certain encoding tasks compared to my dual core. The software has to be optimized to use multiple cores of course.