I don't want an address, they should be cheap, meaningless (sans routing, the longer the common prefix, the closer geographically you should be) and not conflated with identifiers.

I just want a way to do public-key based discovery. I'm not sure if wireguard + DHT would do though as it'd also mean that it's easy to track your PK (and maybe you through your devices/services announced with PKs).

Maybe you can announce your IP in a neat encryption scheme that adds some privacy without increasing costs too much?