Perhaps a prerequisite of the major would be demonstrable knowledge of 2+ programming languages that exist in nearly orthogonal domains.
I think low-level to high-level, with the right amount of history, is the best way build rather than relying on mysterious abstractions below. Microcode, assembly, C or Fortran, are the fundamentals CS graduates should be required to have or the accreditation bodies aren't doing their jobs.
Also:
If you can teach monads, you're a great lecturer.
If you're Sean Davis from UC Davis, you are/were a great lecturer.
A great lecturer of technical minutiae both has an expressive personality and explains concepts as simply as possible using learning aids such as analogies, examples, and diagrams.