Teaching Critical Thinking In answers to a previous question, a few people suggested intro programming with true novices might not be the best place to introduce critical thinking/planning skills for programs. To me, intro programming is the perfect place - many of these skills relate to the ideas of breaking problems down (which tie in nicely with loops), abstraction (e.g., methods/classes), and so on. Particularly with many students only taking intro programming as part of a degree for an unrelated field (e.g., physics, math) in the hopes of being able to do some application-based work, I feel that students would benefit from these skills for such projects.

I am certainly open to be convinced on this topic! Should these skills be explicitly taught in a CS curriculum? If so, where?
First, Critical Thinking is a deep concept and in a first course only simple aspects of it can be taught. To explore the depth of it you need to have context and a novice, by definition, has little of that. See Wikipedia for a start on understanding how broad and deep Critical Thinking really is. 

To me, the most important question to be answered by Critical Thinking is "What should be built?" (and what not built). But a novice has no basis on which to answer such a question. They have enough to do to try to understand what can be built at the start, so you can only give a glimpse of the deeper questions then. 

I would suggest that any true education explore Critical Thinking in many ways and in many courses - philosophy, history, .... And that later in the CS curriculum the topic be taken up, again in several courses/classes to explore its complete depth. 

However, the detail in your question seems to indicate that you are more interested in Deep Thinking rather than Critical Thinking as such. I'm a big believer in teaching problem decomposition and abstraction from the first days. My courses delay if and while constructs for as long as I can manage while the students think about abstraction and polymorphism. I don't always do it, but prefer to teach recursive thinking before loops and polymorphism before selection. That is true even in a course in Java. It doesn't require Scheme.

But some aspects of critical thinking are useful to novices. For example, the idea that if what you are doing isn't working, then do something different. Also "Ask for help" when you are stuck. "Don't make assumptions" is another good idea that can be taught fairly early. "Test your assumptions."

Ultimately you want them to use evidence based decision making, of course rather than wishful or magical thinking, but that, as I said above, requires context and some "seasoning." Novices are naturally focused on the "how" rather than the "what" - especially the "what is appropriate" and "what is important."