One thing some companies do, is require X of Y characteristics.
i.e. Your password must be at least 8 characters long, and contain at least 3 out of the following 4: {lowercase letter, uppercase letter, number, special character}.
So your keyspace is far larger than: Must have a lowercase, uppercase, digit and special character. I think it's a nice compromise - but of course as this report shows, a hacker would still probably target [a-z0-9]{8}.
What would be interesting if the change password form predetermined the password requirements for this particular password, and these requirements are randomised each time the user wants to change the password. E.g. one time it may require a password of at least 8 characters, the next time it might require it to be 10 characters. One time it may require digits, another time it may require special characters. So an attacker in this case couldn't rely on a large populus having simple passwords of the bare minimum length as the system forces some variances in those minimums. Sure, it'll probably piss off users even more... (And I'm the first to admit I'd be pissed off by such an approach too).