I think the higher universities with older programs would be more inclined to teach theoretical than younger programs just starting during the dot com boom or during the past few years.
I felt like it was an excellent program. We spent all of a semester on C/C++. My program was heavy on the math (Calculus, Differential Equations, Linear Algebra, Statistics, and a few others I can't bring to mind). We studied algorithms, number systems, analysis, and all sorts of topics.
The amount of time we spent 'learning to program' was minimal. Maybe I was lucky, but I have to imagine it's hardly different for the majority of programs.
"One year of science and mathematics:
1. Mathematics: At least one half year that must include discrete mathematics. The additional mathematics might consist of courses in areas such as calculus, linear algebra, numerical methods, probability, statistics, number theory, geometry, or symbolic logic."
(http://www.abet.org/Linked%20Documents-UPDATE/Criteria%20and...)
MIT requires differential equations or linear algebra and no statistics (although I think they used to before the '80s) and of course discrete mathematics which is one of the things I'm sure you're not bringing to mind. (MIT does demand a relative high level of mathematical sophistication, every undergraduate must take or place out of single and multivariable calculus in their freshman year (where it is taught at speed), and SICP/6.001 and 6.01 both use math freely (in 6.01 at least as initially taught you have to use differential equations right off and they don't assume you've previously thoroughly learned them).
I've worked very closely with a UVa Applied Mathematics graduate who was taught C++ (but not C, I taught him the new/malloc distinction :-) back in the early-mid 90s. He's not as good a programmer as I am, but he's very solid and most importantly understands what he's doing and the implications of it. Our designs don't fail because we e.g. didn't realize or think correctly about scaling issues.
The problem is that student demand isn't for CS. Student demand is for Information Systems and Software Engineering. Schools either respond to that demand and turn their CS programs into glorified trade schools, or they keep CS as an applied mathematics program like it's supposed to be and risk angering new grads (e.g. "I didn't learn anything useful in my CS program!")
(Sorry about the multiple login, I mistakenly logged in with clickpass last time)
I agree with Zed to an extent, but only because so many CS programs focus on the wrong things and are little more than trade programs. For most young people I meet I strongly recommend they steer clear of CS unless they're going to a school with a proven program.