We of course the best way is to stop using IE!
I've tested in IE6 and see that the .main-col needs to be floated, so add the following to your CSS file:
I don't see the logo issue. Since you're using an image, try removing the h1 tag like this:
<div id="logo"><a href="<?php echo $this->getUrl('') ?>"><img src="<?php echo $this->getLogoSrc() ?>" alt="<?php echo $this->getLogoAlt() ?>"/></a></div>
And then change your CSS to:
Let me know if that takes care of it. There may be spacing issues but they'll be easy to fix!