The sidebar should be cached as well. It's the entire pageload. Note that anything NOT client-side JS, or php-as-image subloads, etc., will be static-ized and not dynamic.
Your main page is 100K. Your images are 323K. That's a lot of data.
I'm not altogether sure why the sidebar takes so long to load -- I don't know when the JS code executes. But yes, it takes a while even on a refresh. Something's not quite right. Definitely stop 'stealing' images from outside sites, run them locally, and compress them more. And of course it all depends on the server load/speed at some level.
Something's amiss, as it looks like my browser is slow to reload images. Maybe something in cache settings somewhere is forcing more to be reloaded and not cached as it should (that's outside of wp-cache).
If you open up the html/source view in FF, and refresh it, it refreshes near-instantly. So it MUST be JS, images, flash, etc. slowing things down. Try turning off a bunch of the extra junk, plugins, flash, on the page, see if that helps. If it does, turn things back on one by one until it starts getting really slow again.