how can we write a policy that encourages people not to use bad
passwords but does't accidentally exclude good ones?
You need to understand two different things:
- what a good password is
- how users think about and deal with passwords
Your best bet, quite honestly, is to get someone in who has done this a couple times. A consultant or security architect. I'm not saying that because you could hire me, but because I've spent quite a bit of time at quite a few companies refining and improving the template I use and know which parts to adapt and which parts are non-negotiable due to security impacts. You're not likely to get that experience with one case and a single policy.
That said, if you want to roll your own, you first need to shed old and wrong conceptions. All these password complexity calculators are nonsense. I've so far always found something ridiculous that will pass them, and most of them are based on the wrong assumption that the attacker will use brute force as his method.
To get user acceptance, you need to find a scheme that doesn't put a burden on users. Frankly speaking, that's almost impossible, as both highly complex and very long passwords are a chore to type, especially if you need to do it multiple times a day. Using alternative authentication would be better, but here we are.
So once you see that "p4$$w0rd" isn't actually more secure than "password", you want to encourage your users to use non-trivial passwords and here's the catch: The more rules you write about what a good password is, the more you actually reduce the space of possible passwords. If I as an attacker know your password policy, I don't have to test any passwords that don't follow it.
Some specific guidelines:
Words are good, if you have enough of them, because people can type them fast and easy, which reduces the dangers of shoulder surfing. They are also easy to remember, which reduces the danger of them being written down.
Names are better, because they are less likely to be in a non-extensive dictionary, especially when it isn't person names but place names, pet names, historical names, foreign names and all that. And they are also typically easy to remember.
Numbers are ok, because they add a bit of variation, are easy to remember and type and can be used in passphrases ("we ordered 4 pizzas").
Special characters are complete and utter bullshit. They are harder to type, if you require them people will typically pick from the 10 or so that they can easily reach, which means your complexity is much less than if you used numbers, they are difficult to remember and are the easiest to shoulder-surf. And the few easy ones, like .,-!? in their logical places in sentences in a passphrase add about one or two bits of entropy.
What you need to do is run your own password checking. I quite often recommend to give people freedom to choose their own passwords, recommend passphrases, and run every new password picked against a blacklist of the top 1000 or so passwords plus a hundred or so company- and country-specific ones and their permutations. If the password is on the blacklist, it is too weak and the user needs to pick a new one, but at least they know why.
Then run a common cracking tool against the hash database at night and every password it discovers is set to "force password change on next login" with a message explaining why.
One more thing: You do want to be careful with the regular password change rules. The truth is that if you have a 30-day expiration date on passwords, 90% of people will have "password1" the next month and "password2" the month after. If you disallow consecutive numbers, they will use 1, 3, 5, ... instead. Humans are lazy and their password is one of the less important things about their job. You are probably the only person in the company thinking hard about passwords.
Make it easy for the normal user, and they will follow your guidelines. Make it tough and they will look for ways around them.