Maybe this analysis I've just given isn't quite right, but my point is
that we should try to think hard about where in the system 32-bit XIDs
suck and for what reason, and use that as a guide to what to change
first.

Very much this. The biggest reason 2B XIDs are such an issue is because it's incredibly expensive to move the window forward, which is governed by on-disk stuff.