This is a hard problem, Kevin, with no easy answers. But here's a couple thoughts:
1. Whenever possible, don't use passwords. If you can secure your internal and cloud servers using private keys that are physically distributed to laptops, do so. This should be how you handle SSH logins to terminal-based services, for example.
2. Whenever possible, use role- and group-based authentication schemes instead of having common passwords. If your services do not support this, ask for it (professional-grade services should).
3. Make certain your password-sharing scheme matches your actual trust boundaries. If role-based authentication really isn't available, create accounts that represent the roles and distribute trust for them. For example, if there are three people with the power to deploy, then create an account called "deploy" and give three people access to it. Consider creating email addresses for each of these roles and then using server-side aliasing to push it out to everybody that supports that role. (e.g. deployer@myco.com)
4. Make sure you have a fallback plan if you're compromised or you need to revoke access from an employee or contractor.
5. Consider adopting a mnemonic-pattern based approach - say, a ten-word sentence that you all memorize and extend with an unambiguous pattern derived from the name of the service provider.
Remember that your passwords are there to protect you from two different threats: external bad guys seeking to get at your data, and internal misuse (whether accidental or deliberate). Make sure they are strong enough for the former, and restricted enough for the latter. Don't forget the importance of occasionally auditing usage, just so you keep an eye on things.
Interested to hear what other people recommend as well.
-Mike