I'm all for teaching more people how to code, but let's be clear that it's possible to understand a lot about how computers work, and about computer science, without knowing how to program. And if we insist that people learn how to program before they learn how computers work, we will be setting up a barrier that will ultimately prevent most people from learning how computers work. Because most people find coding boring and don't have the patience or motivation to learn all the tedious details required to get programs to work. Why not teach the interesting concepts first as a way of motivating people how to learn to code?
I'll also note that people can -- and many people do -- learn how to program without learning grand ideas of computer science. Learning these grand ideas, like computational complexity theory, will make someone a better programmer. But many programmers never get that far.
I think we can teach basic aspects of how the Internet works to someone who does not know how to code. I also think we could explain basic aspects of computational complexity theory to someone who does not know how to program. For example, I think most people assume that all computational problems are linear in the size of the problem input. Imagine it takes 1 second for a computer to add up a million numbers. If you double the difficulty of the problem, you will double the time required to compute the answer, right? Meaning that in this case, it would take about 2 seconds for the computer to add up two million numbers? That happens to be the correct answer for this computational problem. But the fact that some computational problems are worse than linear will astound most people, I think. For example, for some problems the time required to compute a problem solution is the square of the difficulty of the problem. But it is easy to explain examples of hard computational problems, like the Traveling Salesman problem.
So let's not think that learning to code is a prerequisite for understanding grand ideas of computer science, just as learning to be an auto mechanic is not a prerequisite for learning basic concepts of how cars work.