I hate to admit this, but I actually found Ulead's DVD Workshop to be the most flexible, and it beat Adobe's app hands down in my book. It allowed me to customize more features than I knew what to do with, but was very simple and straight forward to use.
I didn't like Encore, because I wanted custom menus. Encore does allow you to sort of change things, but it seemed to only give you a small selection of presets. Get the trial for Ulead DVD Workshop, and try it out.
Currently I am using encore and finding it ok although somewhat of a buggy program to work with. You really need to pull stuff into photoshop to customize.
Odd to hear someone mention DVD Workshop Captain Quirk. You don't hear much about it although it is a great progam and ulead has all but abandoned it. I thought it was great and the interface was fun to work with as opposed to Encore or DVD Architect which are very dry by comparison. The main reason I switched from it was because I wasn't sure if it was handling widescreen footage properly. There is no mention in any literature or the help files about aspect ratio at all. The only acknowledgement of aspect at all was the button on the screen that changed it. Do you know if it just automatically detected the aspect ratio?
I tried a bunch of them, and while Ulead had it's issues, it was the one I would buy. And having tried Ulead's editor in my earlier days, I would say it was Apples and Oranges in comparison.