DVD Menu Size

Hi,

I'm new to Creative Cow's forums and also new to Encore. So, I'm working on making a DVD for a film. I've made all the menus and have imported them into Encore. The only problem is that my original dimensions make the menus come out incredibly poor looking. I originally went with 720x480 as the dimensions. It looked great on my 13inch MacBook Pro but after testing it once on a large screen, I went back and changed the size to be the same as the film, 1920x1080. Now the menus are letter boxed just like the film. So, my question is, what dimensions on the menus would be full screen and retain a good quality when viewed on a larger screen?

Thanks!