The last time I changed a password for a service I set it to a phrase that I can easily remember but which no human or current machine will easily guess. I'd say that the only good rule is "Make it at least 9 characters" (which is at least long enough to disallow "password").
In my opinion it'd be better to just find a list of the top 10K passwords and disallow them.
One out of 50 people use one of the top 20 passwords. [0]
I'd bet that over half of passwords used are in the top ten thousand.
Not really. If X is the number of characters your password can be made up of, there are 8^X possible passwords that are 8 characters long, and 8^X-1 possible passwords that are less than 8 characters long. Even here, right on the border, you've only lost 1 bit of entropy (half banned, half allowed), and you win big the moment someone makes it even one character longer than the minimum who wouldn't have otherwise.
The number of passwords that are less than 8 characters long is X + X^2 + ... + X^7 which is significantly less than X^8 for large X.
So your point is even more valid.
Unfortunately, many sites enforce rules that preclude this password style (e.g., must contain a number).