To start, find in your stylesheet.css all references to
Code:
background-color: #FFFFFF;
background-image: url(../images/tile_back.gif);
padding: 1px 1px;
and change to
Code:
background-color: #660000;
padding: 1px 1px;
Elinimating the requirement for an image as your nav bars are mono color you can just define the color. This should change the look a bit and then you can proceed if necessary with adding height statements to those that need them.
You should also create your own template name...you can copy the classic files you are using now to a folder that you name a name you like and edit the template_info file copy to reflect this name then activate in the admin and reset the side boxes. This will help you later.