In the absence of relays it should be trivial for instance admins to follow each other's "discovery" community.
Only admins would be allowed to post to that community and they should publish a post on a weekly basis so that new servers who've just subscribed to their discovery community can fetch the post and show it to their users.
The post itself would contain an updated list of that instance's communities so that users from remote instances can click on them and subscribe to them. If an instance is very large, the weekly post could contain only the recommended communities and maybe some interesting instance stats or information.
Edit: to give some context, due to the way federation works communities of instance A are only visible to users of instance B if at least one person from instance B has already subscribed to that community.
Mastodon has relays to solve the kick-starting problem. But in the absence of relays it should be fairly easy to have a single specific community that's highly discoverable and from where users select other communities that they could be interested in and thus become the first user that makes those communities visible to other users of their instance.
Yes, but that only works once there's one user from the local instance subscribed to the remote community. This is to allow communities to appear on that list.