I just came across this post (which is more than a year old), and I don’t have the time to research if that has been resolved in the meanwhile, so my reply may be completely out of scope. If so, feel free to remove it as unnecessary noise and delete or mute or close it or whatever options there are for the site admins.
However, I’d like to quickly point out, that you’d have a very good solution to “make it super easy to connect to a box without knowing its IP address” if you researched the topics of “ZeroConf”, “Bonjour”, or the Linux implementation of both “Avahi”, which are documented in official RFCs: see the DNS-SD/rfc6763 (DNS Service Discovery) and mDNS/rfc6762 (Multicast DNS) documents published by the Internet Engineering Task Force (IETF).
ZeroConf originally wasn’t designed to work on the wider internet. However, some later extensions (called Wide Area Bonjour) do add support for this. So this CAN also work on the wider internet. However, this (of course) requires to configure a DNS server appropriately: