It bugged me when I was in school that there wasn't an option for Applied CS in my undergrad program. Then I got into industry and found that the majority of my useful skills were derived from subjects that I taught myself to make me a well-rounded engineer. I felt a little short-changed by my education.
However, as my skills aged, I found that I was leaning more and more and my theoretical skills to supplement my abilities and keep up with the fresh meat that came behind me. As I moved up, practical skills were pushed aside as I made use of concepts to help design and diagnose the systems that I develop.
In short, like most things, the real answer isn't 'either/or' but rather both. You need to give the students a full tool box that works now, works later, and provides a way to make the box bigger quickly and easily. And a student that doesn't want both sets (theory and practice) probably shouldn't attempt either.