What program was this? It sounds much closer to what I wish my CS degree had been. In my CS program, the courses I actually enjoyed were the math-heavy, but always optional, like computability/decidability/complexity, cryptography, etc.
The mandatory "practical" courses were often much worse. For example, I studied relational algebra on my own, plus a few chapters from Kleppmann's Data-Intensive Applications book, and it was painful to realise how shallow it made the mandatory database course look.
I agree that CS should not be mere job training. I think many CS programs are neither rigorous enough to feel like math/science and prepare you for proper academic work, nor practical enough to be good vocational training. They sit in a bad middle ground, where academics teach industry-lite.