Maybe a good way of freaking users out (and educating them at the same time) would be a notice saying "it will take n minutes/hours/millennia for someone to hack this password", rather than the "weak - strong" indicator you see on most sign up pages.