MTPaginate is a beautifully well-thought out plugin. Movable Type still writes all the entries to the page, but MTPaginate inserts PHP code to only display the content indicated as being on the current page, according to a querystring argument. And the plugin provides scads of options for page navigation — more than I bothered to figure out.
The end result is much improved. The software category, for instance, is a 545KB file sitting on the server (it has over 500 entries), but by chopping it up into 15 entries per page, the biggest page anyone can ever download is about 75KB.
Not a perfect solution, but certainly better than where I was.