I'm at CU Boulder, and they've done a pretty good job with the CS course. Freshmen are required to take a "CS As A Field Of Work And Study", which introduces both workplace concepts and some of the underlying theory of computers.

I'm currently taking a "Discrete Structures" class. It's a 2000 level course, and it's all theory. And it's fun.