Header Design Help

I need to design a new header, with a navigation menu.

A site that has pretty much what I think will work is.. superpages.com ..

This is a site owned by Verizon.

A few things I like:

1. Color choices. The left menu back with white text stands out well.. the header menu red also stands out very well, and the content, white background makes for a good combination.

2. The header is user friendly and flows well with all their pages..

What I don't like is the width of the header. It takes up to much space and pushes the content down.

My site is city-yellowpages.com if you do a search of the same white pages you can see the results pages do not have a header allowing for more content.

I am now doing a re-design that will use a header with menu of the items currently running down my left menu.. this will free up the left side for new content.. right side will be used for badge ads (maybe).

Anyway I am asking for input on a good header menu idea (not java, or graphic tabs) .. and colors.

Many Thanks