Well, I just took a look again at the source of the first page.
*edit I think Tijmen's comment was from when he saw the <style> tag with the styles for the menu, and when he saw all the "style="float: left;" in the HTML-- you do have an external stylesheet, however your positioning like floats are in the HTML meaning they are not getting cached per page-- every time the browser goes to a new page on your site, it has to load the HTML because it's a new (to it) HTML document. Everything in your external CSS only gets loaded once however, which can result in subsequent pages loading faster after the first, initial page is loaded. You can set all those internal styles into your external stylesheet and on those with slower hookup to Teh interTubes will notice a difference in speed (all other factors like server load etc. being the same). And yeah, having your styles for positioning in the HTML might still be IE's problem.
Your images are referenced locally, so that's not the problem.
You have a Byte Order Mark before your comment in the CSS. I didn't see it when viewing your CSS directly in the browser (by typing in the full url to your css) but when viewing it with the Web Developer Toolbar in FF, I see this:
[b]ï»¿[/b]/* Reset */
html, body, div, span, object, iframe, h1, h2, ...
That funny little character is how the Byte Order Mark gets represented. It should not be there. Some text editors like Notepad add those in, and you can't see them, because it's not really a character but something used with UTF (though it's completely not necessary for UTF-8, only UTF-16 or higher). The Byte Order Mark tells computers which way to read a number (where the ones, tens, and hundreds places are, left-to-right or right-to-left?).
You could try to open your CSS in another text editor of some kind and see if you can remove that mark. Who knows, it could be what's tripping IE up. You certainly shouldn't have it in your HTML or CSS sheets (I looked, I copied the HTML and pasted it, I don't see the mark anywhere in the HTML so that should be ok).
IE6 sometimes flickers images used in image replacement, and this has something to do with either Haslayout or caching problems... I remember someone talking about the flicker and there was a solution for it. However that's only for some images and I don't think it's the same problem you have.
I do notice that in FF, with scripts blocked and everything, the page was still loading after a long time (even after finally the bg image appeared). There may be something else going on that makes loading take too long and other browsers are covering up for it with caching?