Good luck, this won’t be easy. Even if you do manage to make something that works in more than one browser, it will mostly like break the layout if the user scales (zoom) the text size. I use a similar layout on my site, http://openvein.org/ and if you change the text size, the layout still looks fine - in both IE 6 and Mozilla. Of course thats only because I gave up trying to get horizontal borders to overlap.
I managed to come up with a version of your page that did look right in both IE and Mozilla, but it relies on pixel-perfect positioning and if you scale the font size the menu items go all over the place. The idea was to shift the menu DIV to being the first child of the main DIV, and absolute position the menu DIV to render in the margin of the main DIV. Besides the text scaling problem, I had to specify a transparent border on the menu DIV to get Gecko to render it.