I came across a bunch of cool navigations that sites had been using.
My favorite was from Utah.travel. They use four small textured tabs on the left side of the page. What I found interesting was that when you hover over each tab, a larger box appears behind showing either thumbnails or more information. Also they have a special tab, which makes it possible to choose your own theme for the site, depending on which type of vacation you are interested in.