But why should the average person know how about "low level stuff"? A CS major should know the the level of gates and boolean logic but deeper than that why? Intel's cofounders weren't CS majors, one was physics and the other chemistry.
I agree. Unless the CS major is planning on specializing in embedded software, things like complexity classes and database normalization would be of more use. Even that is overkill, as in my experience leveraging and utilizing software libraries in the correct way often has already solved the issue at hand. Nowadays even more high level skills as that such as networking, caching, and distrusted computing are of more use when it comes to optimization.
For the same reasons they teach everyone history, math, languages, and the arts -- you should know on whose shoulders you stand.