Nice research - obvious results
A nicely conducted piece of statistical research, telling us what we've actually known for years. The entire "character set + template" approach to authentication credential creation is well recognised by both experts in systems and psychologists to be flawed, but we're stuck with it because the people defining login requirements currently have no understanding of either.
The silliest recommendation after "character set + template" is the supposedly random character string. This is grounded in a misunderstanding (and misapplication) of Shannon entropy, and fundamentally fails because (even if generated by a true random process) no-one (OK, maybe one in a million) can remember it. It's actually impossible for a human to create because the mind can't wrap round true randomness - what looks like a "random string" to a human is usually biased to emphasise a small subset of the possible code space.
Even the random word sequence advocates ("horse staple ...") have it wrong. The essence of a robust authentication credential subsists in three requirements:
 it must be long enough to make brute forcing hard - the required length will change with time and the criticality of what is being protected;
 it must be memorable to its creator - so in principle it must mean something to him or her;
 it must not be readily guessable by anyone else - so a problem arises for folks who are not very original ;-)
Within the string space fulfilling these three requirements, the strongest strings against guessing attacks will be the ones that conform least well to a common template. So the best rule set will contain the fewest, simplest rules. Here's my take with commentary in square brackets:
"A logon credential [note that we intentionally don't say 'password'] is not to allow you access to our systems - it's to prevent anyone else gaining access by pretending to be you. It must therefore be easy for you to remember but difficult for anyone else to guess. To achieve this, here are some basic guidelines:
 think up a memorable but not well known phrase or sentence of at least four words totalling at least 15 characters [reasonable length at time of writing, but may need to increase]. This phrase should mean something to you to make it easy to remember, so be imaginative, consider using humour and/or your native language.
certain obvious words are blocked and therefore cannot be used, including [e.g.] your user name, the company name or date words (month and day names) [but keep the excluded words list to a minimum to avoid user frustration].
 you may, but are not obliged to, separate the words in your phrase with non-alpha symbols."
Not the ultimate maybe, but probably a better start than the standard rules that render all words in any dictionary illegal (rather a challenge for a literate user) but permit 'Pa55w0rd!'. I've written about this elsewhere (http://intinfosec.com/library/policies/2011-Instant_Compliance_for_a_Grand.pdf)