First I'd start by bringing the size of your banner down. It's a general rule of website design that you create the site design based on the user, and these days, 1024x768 is the "majority" whereas 800x600 used to be (according to the W3C). Simple fact is that Joe User probably doesn't have the same gear that designers / coders do (Like not many users run dual widescreens like I do at work).

What you probably want to look into is designing your skin to scale. To do this, you would use relative widths for your DIVs, Spans, and Tables (ie width="80%" vs. width="770px"). Doing a skin like this can be a bit tricky if it's your first time or you're not too familiar w/ CSS but the results are well worth it IMHO.

~SB