A designer said to me once, just make what you really do want other people to see, but use only elements that you think  must be on a page.

The saviour of people like me is the cache. Provided the visitor can hang in there for the first few pages, the rest will download much more quickly as all the assorted navigation graphics get pulled out of the cache. A possible strategy is to introduce a small number of new graphics on each page while reusing as many out of the cache as possible.

Graphics though aren't the only offender. The rollovers and html code for the layout across the top of this page weigh in at about 20k, excluding the graphics!! terrible really.  Are they worth it? hmmm. I'm stuck with them for now till I come up with a better solution.

Will you weigh each page individually or look at a page size average? I use the second method because it is much more forgiving! And what limit will you set?

I've only received a small number of complaints regarding download speed. The feedback suggests to me that people are happy to wait longer if they know the content is good and will be there.

Slicing main navigation graphics up is a good strategy for maximizing usage of the cache. Often similar elements will appear across pages, with only small changes. Forward planning allows you to design graphics where the sections of a graphic that change from page to page are of minimal size, with the rest of the graphic remaining constant - i.e. being served out of the cache

Slicing images also helps give the illusion of faster download speed.  Graphics are appearing giving the user something to look at. While in fact the overall time is similar, if not longer, than single large graphic files, the user is being given image snacks eat, rather than waiting for a whole meal! Try it yourself!!

It is your call!