What options are available to use a remote VPS to facilitate connecting Wireguard directly through the CGNAT? It seems most "client" devices are going to be behind at least some kind of NAT as well.

STUN and TURN is what tail/headscale use, basically you can use whatever you want to map ports but if you want to hole-punch you are probably going to have to use something off the shelf or write your own client to integrate wg and the hole-punching logic.