While Computer Science is a vast and complex domain, at its heart, the basic notion must be that of a program. To understand software of any sort, you need to understand something about the programming process - a process that is as yet not completely understood even by those who study it.
A program is itself a mathematical object - it may not involve any real numbers or visible signs of what we normally consider mathematics, but it is inherently mathematical. The process of naming an object in the program and the way that that object is then manipulated, is an algebraic process and the same kinds of rules that goven algebra apply in programming. A program is also a ``construction'' (almost in the sense of the Euclidean Geometric constructions) - it defines a set of steps that are taken to ``construct'' a solution. Someone wishing to read and understand a program then needs to understand the rules used in the construction, and then to puzzle out what the bits and pieces do within that framework.
But while this view is one way to look at the program, it is limited in that there is no good way to ``prove'' a program correct mathematically. There are ways to prove small pieces of code correct, but the effort involved is often huge (a famous example is of a twenty line program that was proved correct in about forty pages of dense mathematics). The validation process is far more akin to the social process that mathematicians use to study and verify a proof. It is a process of convincing other readers of the program that it is correct.
But a program is also an engineering construct. There are correct programs that are unusable - often because the solution would take far too long to compute exactly - would you be willing to wait 10,000,000,000 years for a solution to a problem? There are programs that are known to be incorrect but that are usable as they run fast enough and give answers that are ``close enough'' (or perhaps that have a probability of error that is very small - say one in 2200) These tradeoffs are essentially what engineers do and engineering skills are required. In most engineering though, the basic knowledge has been around for quite a while, even hundreds of years. Programming as we see it now has only been around for fifty years and we are still working to codify the process and even find ways to measure it.
Another engineering factor is the language the program will be written in or the system it will run on. Programming languages are difficult things - easier to learn than natural languages (English, French...) and requiring very different skills. Still, programming languages are not completely understood mathematically and they can be quite large and difficult to understand (the C++ Draft Standard is almost 2000 pages long - and this is a formal and relatively concise document). The operating system (Windows, Unix, VMS) is another factor, and finally the hardware below everything must be considered (arithmetic does not work the same way on all computer hardware).
Programming is also a social process - usually involving groups ranging in size from two or three people to many hundreds and the rules involving these groups are (again) not well understood, nor is the interaction of the group with the software project. Software projects often fail because of mismanagement. While there is a developing knowledge base on how the process works, for the most part people work on the basis of folklore and a few well understood ``proverbs'' : ``adding people to a late project only makes it later''. (There may also be legal and ethical issues to cope with here - suppose your boss says to do something that you know is safety critical. A refusal can lead to dismissal - but going along may lead to much more serious legal problems down the road.)
Programming is also very much a psychological process. We have come to realize that there are no bugs in programs. The programs do exactly what the programmer told them to do. The bugs lie in the programmers mind, perhaps the wrong problem was solved, perhaps the right program was solved in the wrong way. And there are common errors - involving typing errors, building an arithmetic expression with parentheses in the wrong place and so on. When the programmer detects an error (itself not a trivial process) in the program (the output is incorrect, for example), the search then begins for the portion of the program that contains the error. This can be quite difficult - as the person looking for the error needs to overcome the very strong tendency of the brain to see what it expects to see - not what is actually there. For example, the programmer might have written ``x = x - 1'' (subtract one from x) instead of ``x = x + 1'', but if the programmer expects to see ``x = x + 1'' that is what will be seen contrary to what is actually there. (In labs, helping students to find such bugs, I often ask them to read the program character by character aloud and many times they will read the expected (but incorrect) version instead of what is actually written. Sometimes they will have to read the text over four or five times before they see the problem.)
It is unreasonable to expect to teach any large part of this to students in four years of college - especially when they have other requirements and other demands on their time. It is the more so when you realize that along with the basic programming skills, the CS major also needs to know something about the various software technologies used in many places - things like networking, computer graphics, numerical methods, algorithms of various sorts, computer hardware, operating systems, perhaps four or five programming languages, software engineering practice (such as it is) and lots more. And then there are the new developments in the field.
Indeed, the most important thing to teach in computer science really concerns the brain of the programmer (or software designer). Learning how to distrust your mind enough to find errors (as above) is crucial, learning how to interpret formal software documents (like technical manuals and the like), learning how to somehow read and understand a complex piece of code. And most importantly, learning how to learn. In my time as a professional (not academic) programmer, I have programmed in at least a dozen different languages and on as many different computer systems. I learned several different subject domains (network protocols, expert systems, VLSI design, Web scripting, computer graphics, network security). Not all programmers will see as many different kinds of problems, but in a field where the average stay in a position in industry is only three years, our students must expect to learn quite a few new things over the course of their careers.
Anyone can learn this stuff - its tough, but its feasible. To do it well though requires a balance of mathematical skills and engineering talent. If you look at the number of people who feel comfortable with both math and engineering, its clear that only a small percentage will do it well and only a very, very small percentage will do it very well. Contrary to popular belief the best software people are very non-linear thinkers and have a certain talent to grasping both the gestalt of a whole program and at the same time the details involved in the lowest level implementation.
One of the goals of building a good computer science department involves getting enough of the good students and (one hopes) enough of the very good students into the department to generate the right cultural atmosphere - one in which the students are challenged to do their best, where they can find other students to help out, and where people are genuinely interested in the field - enough so to spend time reading the right web sites, playing with software and generally fostering experimentation and exploration. This mix of students also makes undergraduate research projects feasible - as the best programming teams tend to be composed of a majority of good programmers and one (or a few) of the very good ones. (The analogy often used is that of a nuclear reactor - you need both the fast neutrons and a buffering material to produce a nuclear reaction.)