I am so tired of people saying, "Well you have to have math because you have to have logic." Logic is separate from math, and math is largely concerned with inductive logic...You know, the kind you never use in CS? In all the math I've had in my life, the only kind that had deductive proofs of the sort that resemble programming logic, was 10th grade geometry. I started CS via Cognitive Science, which is largely Philosophy. I had more, and more relevant, logic courses in Philosophy than in CS or math, and it gave me a huge edge in programming over my math-centric peers.
I've been in the field for 15 years, and I've never used a single thing from advanced math. I used some pre-calculus once, to figure out how much air conditioner I needed for a server room. I had to take 3 semesters of physics too. What the hell was that about? At the same time, I only had a single course in network theory, and it was obscenely general, with LANs mashed up together with the sort of latency issues you'd only run into if you were networking satellites.
I agree as far as teaching theory...That's all I was ever taught, and it's served me well. But advanced math isn't useful for the vast majority of CS majors.