It's amazing how much of this is alleviated by something like 1Password or LastPass which I currently use. It'll generate a strong random password for me and remember it so I don't have to write it down. Changing passwords is just as easy.
Go to a site, go to the account page, asked 1Password to generate a new password, 1Password detects what's happening and asks if I want to update the login info, go to next site.
I was able to change the password for all my important accounts in a matter of minutes.