Answer: It was, in fact, performing reverse DNS resolution. Based on the suggestions below and this article, I added "UseDNS no" to my sshd_config, rebooted ssh, and now the password prompt displays immediately.
When I SSH into my server I am given the standard "login as:" prompt, followed by the "user@host's password:" prompt. For whatever reason, the second one always takes a while to display. My server isn't under any load and typically executes commands quite fast.
Now, we're talking only 10 seconds or so between the time I hit Enter for the username and when the second prompt displays, but when you do this a lot it gets annoying. I suspect Ubuntu is looking up my user account, but it has < 5 accounts on the entire installation.
Update @Josh /var/log/messages does contain this gem:
Oct 28 16:54:59 Athena sudo: pam_sm_authenticate: Called Oct 28 16:54:59 Athena sudo: pam_sm_authenticate: username = [msmith] Oct 28 16:54:59 Athena sudo: Warning: Using default salt value (undefined in ~/.ecryptfsrc) Oct 28 16:55:01 Athena sudo: Passphrase key already in keyring; rc =  Oct 28 16:55:02 Athena sudo: Passphrase key already in keyring; rc =  Oct 28 16:55:02 Athena sudo: There is already a key in the user session keyring for the given passphrase.
Where msmith is my username. What does this all mean?