Thank you for your help. There were two problems. The first problem was the missing Doctype, and the second was the way I was using the <div style="clear:both"> tag.
The reason it worked in IE and Opera but not in Firefox and Safari seems to be the way each browser handles clear. The footer (where it has the copyright info and phone number) appears in the code below the sidebar links. The clear pushes it down so that it clears both left and right columns before being displayed. The difference between browsers is whether it forces its background css on the area from where it should have started without the clear to the area where it does start.
All I did is put the navigation bar's background color into the footer CSS.
So that fixed the problem. :) Thank you!
The second issue I had to clear up was the screwed up looking login box, but that's fixed now too :)