Re Complexity
"I wouldn't have thought that "ilovebakedbeans" is harder to crack than "Cj4$Vf7^""
Except it isnt, unless the attacker is doing a dictionary attack which has the phrase "ilovebakedbeans" hard coded into its data store.
Even if the attacker uses rainbow tables, the question is how long are they going to keep attacking.
If your password is subject to dedicated attackers who can resource long term attacks (eg. its the access password for the nuclear launch codes and its hash has fallen into the enemy's hands), then you need very long, very random AND very complex passwords. (note, there is an element of contradiction there).
If this is a normal password, even an internet banking one, then length trumps complexity. Most attacks appear to aim for about 8-12 character passwords. It takes too long to try the possible alternatives that longer passwords offer.
This is even more difficult for the attacker if there are no rules on what your password can be. As others have said, if you demand one upper, one lower or one number then you REDUCE the possible number of passwords an attacker must try.
For reference: (assumes an attacker can try 1 billion combinations per second)
A 15 character, all lower case, password has 1.6 sextillion combinations and would take in excess of 50,000 years to brute force. Example: ilovebakedbeans
An 8 character complex password has 7.2 quadrillion combinations and will likely be cracked in under 84 days. Example: Cj4$Vf7^
The best rule of thumb is to set your password policy as 18 characters made up from any ASCII printable character and dont restrict what people can pick - so they can have all letters, all numbers etc. This gives you about 4x10^35 combinations and would take about 1x10^19 years to brute force.......