I was finally able to figure out what was going wrong by using an nTap device and WireShark to capture the mDNS traffic being generated by the device both by Avahid and by my own program. Since avahid didn't generate this problem, presumably the responses generated by avahid were the ones Linux was looking for. I updated my program to generate similar responses and that made the 5-second delays go away.
In particular, the reverse-mDNS responses generated by avahid contained 0 queries and 1 answer (of type hostname) only, as shown in the attached wireshark screenshot.