Okay, I resolved my performance problems with Unison. It seemed like it was taking far too long to search for changes; I noticed that it paused for significant lengths of time on extremely big files. If there are no changes and the archives files are intact, then it should just have to stat the file, so the time per file should be constant, not proportional to file size.
But this wasn't happening. Then I realized that my recent disk reorganization probably had something to do with it. I installed a new disk, then repartitioned and moved file systems around on my home machine recently (more on that later), and this of course changed the inode numbers on all the files, which unison tracks in its archive.
Now, my expectation was that unison would be slow the first time around, but after noticing all the inode changes, it would be fast thereafter. This didn't seem to happen. After a full sync (which was painful because I had to do it in pieces to avoid the dropped ssh connection), I had to delete the archive files, and then resync (again, in pieces). And now the new archive file has the new inode numbers and the normal sync is fast again. Yay!
Or, at least that's my model of what happened.