Reminds me of a quote from one of the most famous Computer Scientists, who was really a mathematician:
"Computer Science is no more about computers than astronomy is about telescopes." - E. W. Dijkstra (1930 - 2002)
I would imagine that a comp sci department where they never reach a point where the "rubber meets the road" is not worth the trouble.
...unless your rubber has already met your own personal road long ago. I, personally, learned everything practical I needed to know about programming long before I stepped into a CS class, mostly from self-teaching and the web; I only took CS to "straighten out" my theoretical knowledge. I would have loved a CS department with no computers installed (except perhaps for interactive debugging after it's already clear that you can express yourself in pseudocode.)
Avoid classes that teach syntax, unless the syntax is used to highlight a language feature you have never encountered before, like continuations or currying.
In my CS classes they had exercises, but students where left on their own with the details of programming. OK, there might have been dedicated courses on "how to solve the exercises", but still.
My first day in the computer lab I was completely lost, because I had gotten into Computers with Commodore C64 and then later DOS+Windows 3.1, and I had no idea how UNIX works. Other times, though - WWW was in it's earliest infancy, today it is certainly easier to get information on UNIX.