Multi-region redundancy costs an arm and a leg

Yes, if you buy an off the shelf solution, it'll be expensive.

I'm suggesting treating VPS instances like you would a colo setup. Let cloud providers manage the hardware, and keep the load balancing in house. For Signal, this can be as simple as client-side latency/load checks. You can still colo in locations with heavier load; that's how some Linux distros handle repo mirrors, and it works well. Signal's data needs should be so low that simple DB replicas should be sufficient.