Wow, what a nightmare. I have read absolutely everything on this subject and everything that has been suggested so far was tantilizingly close to what I was experiencing, but none of the solutions worked for me.
And I figured out why.
Unlike others, I was not using /etc/hosts to set up local domains. My /etc/hosts file was stock, containing only the entries needed for the loopback interface and the broadcast host. Moreover, it was a correctly-encoded unix file, as I'm the sort of person who would only edit that from the command-line using emacs. And, thank goodness, I did not have to resort to running my own DNS server like DNSmasq to get around the problem.
(To be clear, the symptom that brought me here to this issue was that emacs took about 10 seconds to start, but only when I was on wifi. If I turned off wifi, emacs would start up instantly as expected.)
My solution: my laptop has a name, "terminator". (Yes, its shiny aluminum exterior made me think of the Arnold Schwarzenegger character.) I just needed to add entries to /etc/hosts for the name of the machine itself:
127.0.0.1 terminator
::1 terminator
I found the name of my host by running a simple command in the terminal:
hostname
...which came back with the output: "terminator". After changing /etc/hosts to contain those two entries, emacs can now quickly resolve my laptop's name.
I hope this helps someone.