It's worth noting that some competent organizations actually prefer passwordless sudo when they have users who need to log into lots of different remote hosts—particularly if that includes hosts with varying levels of security.
The problem with entering your password is that you're giving your password to remote systems on a regular basis. One of the reasons we use SSH is to avoid exactly that kind of security hole. It's a question of tradeoffs: you're increasing the likelihood that a user's password will be compromised in order to decrease the likelihood that an attacker who has compromised a session or key will be able to achieve root access. In particular, imagine the following scenario:
- large organization
- many hosts
- hosts have varying levels of security
- non-root access is already harmful
- user passwords unlock many things
In the scenario I've described, passwordless sudo may increase your security by protecting the user's password. This is similar to the password-reuse attacks that have become common on the Internet, except the vulnerability stems from a unified authentication system rather than the actual reuse of passwords.
Unless you're at a giant company, passworded sudo will probably increase your security—but by not necessarily by a great amount. Unless you are really a professional at systems security, or it's a host with nothing particularly valuable on it, I'd recommend you leave it on.