The solution is to just ban common passwords. Start with a list of dictionary words and leaked credentials from other sites, and simply ban the use of said passwords for accounts on your site. That's what Arenanet does for Guild Wars 2. You also ban new passwords as too many people try using them. As for messaging, you just straight up tell the user "That password is too well-known. Try something more creative."
You don't even need to store the password to implement popularity-based bans. When a user enters a new password, hash it and store the hash in a table (just the password hash, not the associated account). Each time someone else uses that password, increment the count. When it hits N, just ban new uses of that password, and optionally force current users of that password change it on login (by checking the plaintext they just entered against the banned hashes). (Meanwhile, store a salted hash associated with the account id for login purposes, to make it harder to crack passwords if your hashes get leaked.)