Change all your administrative passwords to be extremely strong and preferably use Unicode characters in them.
Disable storage of cached credentials on all machines that do not need them.
Implement a password policy that requires at least eight characters and three of the four character sets. Simply using the built-in password complexity functionality in Group Policy accomplishes this.
Start a campaign to teach your users how to pick better pass phrases.
Disable storage of LM hashes if at all possible.
Implement an audit system that warns you of excess login attempts.
Disable the account lockout setting.
Start investigating how to deploy a multifactor authentication system.