Computer Science... I shudder to challenge its meaning and its validity as a term. It's a fairly recent term, which is very loosely defined. The reason I don't want to bring up its ambiguity is that its definition can still stir up controversy.
Personally, I am in the camp that says CS is the study of computation. To paraphrase the late Dr. Dijkstra, "Computer science is as much about computers as astronomy is about telescopes." True computer science is done in proofs, mathematics, theory, not in programs. Of course, some would argue that it is about basic computer programming skills, the ability to operate a computer, and to understand its functioning.
IMHO, these functions associated with computer scientists are side effects, in much the same way that I/O is a side effect of the execution of LISP code. It is a desirable one, but is not the main goal. No, the goal of CS is to study computation, to classify problems according to their solvability as well as time and space complexity. It strives to create new, provable, algorithms. Or, barring that, to prove that no algorithm could exist to solve the problem at hand. To that end, it is a branch of mathematics. It is, in fact, a branch which offers considerable insight into other areas of mathematics.
As far as teaching basic programming skills, I think students stand a bit to gain from that as well. Obviously, theoretical computer science is not for everyone. However, as it was done with me, programming could be a "gateway drug" for the wider world of TCS. As a child of the 80's, when I went through school I picked up BASIC on my school's Apple II's. I showed a lot of promise with it, and so my parents bought me a Commodore 64. I programmed, a lot. The skills that I honed there led me to other skills. Eventually, when I said, "Is there nothing more?", I was shown the way to TCS. I suddenly discovered that programming skills had trained my mind to understand the concept of computability. Soon, I mastered the proof, and now I have the whole of mathematics at my beck and call.
So in conclusion, whether teaching outright computer science, or teaching programming, we stand a lot to gain. Our next generation of computer scientists are in our schools now. The trouble is, many that would be able to do it will probably never even hear the word. I was lucky. I was born during a period when the world was going computer crazy. In our current system, computers are now a matter of course. I often worry that because of a lack of computer education in schools, American computer scientists are a dying breed.
Just go look around at any CS program in the US. I promise that at the graduate level, you will find mainly Asians, Indians, and Russians, not Americans!