Make passwords long, and changed infrequently.
That way, a user can have something like "I like chocolate eggs" as their password.
Artificial complexity rules like "must contain letters, numbers and a mixture of upper and lower case, cannot contain dictionary words or your own name" simply lead to passwords being beautifully chosen and tastefully calligraphed onto the Post-It stuck on the monitor.