If root can log in, the username is definitely known to the attacker and they must figure out the password. If root can't log in, the username of someone with an entry in sudoers probably isn't known to the attacker, so they must figure out both the username and password.

I do like this answer, but I'll also point out that making someone guess two strings is just as secure as making them guess one long string. If root has a random 10-char password, that's roughly the same number of guesses as a user's first name with an 8-char password.

Unless they can read the shadow file somehow, or a specific user attack vector makes it somewhat easier than complete guessing...

I'm not up to speed on security, but it appears to me that your sudo password should probably be different from your account password, so the scenario turns into figuring out the username and two passwords.

Is that even possible? I've never heard of anyone having a separate sudo password.

Yes. Here's how to set a separate sudo password:

Assume your primary user account is called "user".

Set up a second account, whose password you want to be your sudo password. Let's call this account "admin".

In /etc/sudoers:

  Defaults:user runas_default=admin
  Defaults:user runaspw

Now, as "user", you can

  sudo -u root whoami

and you will be asked for "admin"'s password.

The only downside is that "root" is no longer the default user to become, you have to explicitly specify it.

Hm... would the user not being in sudoers and using su with root password being different than the user password make more sense?

To log in via SSH, you (should) have a key, and a password for that key. To sudo on the server should require a different, complex password for the paranoid admin. (So 2 long passwords and a key to gain sudo priv's)