Navigation Bar

I like the first over the second since it doesn't follow the mouse after popping up.  According to the page it's supposed to work with FF1+, IE5+, and Opera 7+.  You do still need a way to have visitors be able to get to the links if they have JavaScript turned off though. 

If you're paying them they better think about that. That's a pretty standard issue that a web designer needs to handle. 

One thing that I've seen done, although I don't really like, is to use a set of <noscript> tags down on the bottom of the page that contains links to all the pages.  That way it shows if JS is off but not if it's on and the navigation menu is working.   

Like search engine crawlers?

Actual human visitors are only around 2% on my site with JS off, but the robots are an important consideration.  If they can't crawl the links on your site then they won't be able to get to your pages to add them to their index. 

Yes, a sitemap will help crawlers find your pages.  But it's still better to have crawlable links. 

The <noscript></noscript> tag tells the browser to display whatever is within those tags if scripting is disabled.  I'm using it on an eCommerce site right now to do something similar to what you're trying to do.  There is going to be a set of dropdown menus that show up when clicked on.  The menu will be a hidden <div> that becomes visible onClick.  Of course without JS then that onClick will never fire.  So I'm going to use <noscript> tags to display the contents of the dropdown underneath the content (that doesn't sound right, but it makes since if you've seen the layout). 

Yup

That's what I usually do.  What browser do you use?  They've got a setting somewhere that gives you the option to disable JS.  If you're using Firefox there's a plugin called Web Developer Toolbar that has a menu option to quickly disable and enable scripting. 

Ryan, the problem with the drop down not following the mouse is that it's some random place on my page.  I don't know why.  I think it has to do with the fact that I am using image mapping to do the links.
Will you take a look:
www.charlesbarnardphotography.com/di/index2.html

Don't have to do the entire site javascript. My site works fine with either (no flash is ugly but still works)

as far as a drop-down menu is concerned, you can buy them or pay someone to build one.

If you can think of a way to NOT use drop-downs, I'll send you snippets from my site you may use.