Thought I would post a quick update. I'm wrapping up implementing the system I've described above, with some updates. It's working pretty well!

First, I've completely eliminated snapshots as a data structure/concept within my system. Each entity just maintains its own rolling buffer of stored historical state images. This sounds more memory hungry on the surface, but it's actually cheaper. It's roughly the number of pointers in memory, but with one fewer intermediate data structure taking up room. Also makes access much faster on both client and server and simplifies code.

With that in mind, I just treat each entity as its own semi-reliable transmission channel. In each client->server packet, the client reports for each entity the last tick that the client received an update on for that entity (this eats a little bandwidth, but it's only a few bytes per entity and server download is much more abundant than upload). Then in each server->client packet, it picks an "arbitrary" set of entities to update for each client, and for each entity picked, sends a state update as delta-encoded against the client's last reported tick. (If it's too old, we full-encode.)

One really nice quality of this is that the client doesn't care and has no involvement in what updates it gets for which entities when. All it knows is that if we haven't heard about an entity in a while, that we should extrapolate for a bit and then set that entity to sleep until we do. The server has free reign to decide how it's going to pack each packet and which entity state updates go in it (scoping, variable update rates, round-robin updates, and so on are all viable to use, though I've now run into the NP knapsack problem). I don't have to worry about scoping hysteresis or anything like that.

Also, I'm using a little trick you might like. The tick count can get pretty big -- several bytes if you have a high update rate and your sessions go on for multiple hours. I don't want to send a full tick with every entity. However, I know that the basis tick for a delta encoding can only go back as far as the length of my buffer (in my case, 60 ticks). So I send the server's full tick once, and then every entity contains the offset from that full tick number (0 to -60). Down from several bytes to several bits per entity. Really adds up in savings.