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?
tcpdump? That can tell you if the server is indeed using all that time by itself, or is actually communicating with the client.