right, having the layout options by choosing a different CSS is a great idea - however, make sure to separate the element positioning from things like font sizes and image stuff, etc...
so that when you pick a different layout, your image borders and font colours stay the same.
to address the navigation stuff, here's the deal as I see it should be:
1) provide the choice to list Pages as nav items or Categories. In other words, set yourself a variable, which you can use in the theme to tell you which template tag to use, so in your theme you might have something like if($navoption='pages') wp_list_pages(blahblah);
Some people might want to list the pages on their site as nav items, others might want to use categories for that purpose - which in my view is often better, but most themes don't allow the choice.
2) people will invariably (eventually) have more pages and categories on their site than they want to display in their top menu, right? So you have to allow them to either select multiple categories/pages to exclude.... or, which I think is better, actually make them specify which pages/categories to INCLUDE in the menu list.
so once they've chosen whether they're listing pages or categories - give them between 5 and 10 dropdowns boxes allowing them to pick which pages or categories they want included in their menu.
Obviously if in the first option they've chosen to list pages -- all they see here are pages. If they've chosen categories, all they see are categories, right?
3) as for actually excluding or including them... this is a little tricky, but not very.
both wp_list_pages and wp_list_categories provide an include= parameter which takes a comma-separated list of either page IDs, or categor IDs. When your users build their list with your dropdown menus, simply store that list as 1,2,3,4,5 etc, and then pull it into a variable for use in your theme...
wp_list_pages/categores("include=$myplugin_menuitems");
...should do the trick then.
4) This is an easy one, but I think you should also provide the option of allowing comments on pages, since they aren't by default.
5) as for link categories, you could allow them to use a link category for additional menu links if you wanted, but I think that adds extra complexity. If you do that, then you need to have them first MAKE a link category, then tell your theme which link category to use... yadda yadda.
I'm saying get them to choose pages or cats for internal links - then provide 2 extra options for linking offsite. Just a couple of text entry fields each, like:
[link title] [web address]
[link title] [web address]
and have them appear at the end of their internal links on the nav bar.
so the nav bar ends up looking something like
[home] [cat1] [cat2] [cat3] [linktitle1]
just to let them link to things like a forum, or their flickr page or whatever. Anyone who wants more than that can set up their own link category and pop it into the header.
this sort of seems like a lot, but the more I think about it, it's not actually that bad. You just need a couple of fields in the options table to store your stuff.