uPnP support?
I don't know if this is possible at all, but is there a way the GNOME remote desktop sharing thingy could detect the availability of uPnP from consumer routers and poke the required firewall hole with it (maybe with a checkbox in the settings panel)?
Then, in that scenario, instead of just telling the user that they can connect to "vnc://the_hostname.local" it could figure out its public IPv4 address and provide that (and maybe with a copy-to-clipboard button in case of the "pretty much unreadable" IPv6).