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.