Taking a step back, what we are doing is essentially: you may choose your own password! But, not really. We are going to tell you what not to. After you try it. And it's not a human, or equivalent AI: it's a (dumb) algorithm.
If you are going to let someone choose a password, ask yourself: why? Is convenience that much more important than security? Putting, what many people will perceive as, onerous constraints on the passwords greatly reduces that convenience. But users will still try to make it as low entropy as possible, so security suffers, nonetheless.
Or is security so important, to hell with convenience? Then why not just generate a PW for them? Here, print this out, since you were going to, anyway. Click "save this password", since you were going to, anyway.
Cut out the middle man and save everyone time.
Now, instead of forcing your users to do the try-to-cheat-the-entropy-algorithm dance, you can show them what a good password can look like. String four words together: happy (or less annoyed) users, good entropy, happy admins.
In addition to the frustrations you've outlined, consider a further case where a user's username is their email address (this was true in the project I mentioned). How is the user most likely to behave in this scenario? Are they going to take the time to generate a new password that satisfies your constraints, or are they going to keep things familiar and use the same password that they use for their email? Afterall, the usernames are the same - so why not keep things easy to remember? Well, I'm sure that's convenient, but I absolutely DO NOT want your email password, even bcrypted/&c., in my DB. No thanks.
Clearly, then, the best choice is to generate something for the user; something that they can reset using a classic 'forgot password' system, but which they never have to define themselves. Four diceware generated words, plus spaces, each no longer than two syllables, seems to do just fine.
[1] https://github.com/dropbox/zxcvbn
[2] https://dl.dropboxusercontent.com/u/209/zxcvbn/test/index.ht...
As a client side solution, that download size seems excessive for a password strength meter.
I understand it contains a dictionary of passwords but that is larger than most JS frameworks. Perhaps a server-based XHR-based solution would be better.
There are secure key-exchange schemes that don't require sending over the raw password, but this isn't an example of one.
The alternative is browser-side encryption of the password before sending but that will get @tptacek rightfully punching you in the face for even mentioning it.
oauth / openid for the win
Unless your companies "secret sauce" is user authentication and management, you probably shouldn't be doing it.
That's even before getting into the question about whether or not such systems make it more likely that users will fall to phishing attacks by conditioning them to enter their credentials somewhere other than the website where they were issued that they went to directly.
It's also not suitable for certain demographics, which puts you back at square one (rolling your own).