SSH and sudo were starting very slowly because /etc/hostname and /etc/hosts did not match. After adding a line for the hostname in the hosts file, the initial 2-4 second delay no longer occurs.
At first I was surpised the mis-configured hosts file caused delays with SSH and sudo. I was SSH'ing to the server with a direct IP address, and sudo did not seem to require a hostname lookup. However, I read they were both doing reverse DNS lookups. (sudo also helpfully reported it was unable to resolve the host)
What other network operations will be slowed down by such a mis-configured hosts file? For example, could a mis-configured hosts file slow down connections to an Apache Tomcat server with Spring hosted on that server?