How would I write a program in such a way that it could discover other instances of itself on the network and let those instances "peer" with each other?
I'm mainly looking for protocols that would allow me to do this (and, hopefully, not put too much stress on the network).
Within a network (=same subnet) you can use broadcasts to communicate. Although you can't be sure that a broadcast reaches it destination (due to firewall protections against them).
I would suggest to use "Bonjour" protocol, which is itself based on DNS broadcast if i remember well. While Apple originated, i think specs & base implementation libraries should be available on several OSes/Languages