My opinions may be a little unorthodox, but here goes.
The catch is that it is a class for all students to take, not just those interested in programming, and therefore will focus heavily on teaching problem solving.
I think this is the most important part of what you are asking. I'd guess that when you ask most people this question, they'll think of the best way to teach computer science, or the best way to teach computer architecture, which will undoubtedly lead to thoughts of "No! Not that language!" and the like.
To teach problem solving using computers, you need to go from a top-down level, which rules out C or assembly. You also need to teach an interpreted language, not a compiled one -- if you want a quick-and-dirty solution to a problem you face, how many times do you pull out Java (or C++ -- I'm not anti-either)? I agree with your choice of Python for this reason. You need something closer to shell scripting, but not to the point of bash; it's not high-level enough and your students will be bogged down with syntax instead of learning programming constructs and problem-solving techniques.
It sounds like you are not trying to teach computer programming, at least not in the way either computer scientists or computer engineers think of it. Computer scientists need algorithmic analysis; computer engineers need architecture and low-level interaction. I understand that this is a cliched oversimplification, and to be really good at either, you need to understand both sides. But if you're not training these kids to be either one of those professionals, your goal is "Problem Solving Using Computers", which happens to require a knowledge of "Computer Programming". They need to know loops, decisions, and variable manipulation; the deeper you delve into computer science and architecture, the better for them, but don't lose sight of what you want them to be able to do on their own after the end of the term. If they walk out of your class thinking "I'll never use this", either they aren't the students who should be in the class, or you aren't teaching towards that goal.