So this is my 2 cents. I used to teach at a private institute but I was pretty young then. Although I had great success.
I got most of my ideas from this book: Accelerated C++
Why is it different? It focuses on why you do stuff. Instead of saying:
"Loops : Its this thing in programming to repeat control-flow..blah blah"
"oh hey, we need to print this line a 100 times, what do we do? Oh we use this thing called loops"
So you go from problem to solution, people figure out why you're doing what you're doing.
It becomes very useful while understanding OOP too, I had students write a procedural, console app in C (a student grade management program) and then slowly convert/port it into C# with object oriented programming. Again, this way they learnt Why you need OOP. Why is it useful.
Other than that I second Chris, like math you need practice.
What I would do is make it as real world as possible, so for a Microsoft Frontpage class I taught, I walked my students through making a simple website of their choice. Over the week each student created something different and they were pretty excited because I told them I would host it online once its done.
Lastly I just generally think you have to love CS to really understand it, its a difficult life being a programmer, code you write is never correct the first time, you debug 80% of the time, the playground keeps changing with technologies evolving like crazy (Moores Law) Unless you LOVE it, you won't do to well.
(I generally started a class with that speech)
NOTE: I never taught any hardcore college level CS. I basically taught programming languages like C,C++\ C#, asp.net etc. And Applied Object Oriented Programming.