(Article author here.) Yes, this is what DERP is for. Nowadays automatically designating nodes as supernodes doesn’t work as well as it used to, since many devices are battery constrained and cloud devices tend to have metered bandwidth. We might someday have a way to add your own DERP relays for your domain (since the DERP code is open source anyway). The tricky part is guaranteeing reliable delivery in that case.
There is mention of STUN, but CGNAT is a whole new level of ugly and there is often NAT behind the CGNAT.
If not, do nodes that can get incoming connections become relay "super nodes?"