I actually studied "Computer Engineering" (rather, literally "Engineering Informatics") at a technical university (with other prominent programs including electrical, civil, and mechanical and chemical engineering) but we did learn all the algorithms and data structures, complexity theorems and proofs lots of math stuff rigorously, but the curriculum grew out of electrical engineering and so we were also close to the metal at the same time.
We took logic design in first year, flipflops, half-adders, built projects with such stuff, learned about analog-digital converters, the Intel 8085 architecture. Physics, to understand electricity (Maxwell et al.) and circuits. We learned assembly, C, system programming, resource management, paging algorithms, scheduling, filesystems (following Tanenbaum), we learned some Verilog and VHDL, but also graph theory (with proofs, plus applications to VLSI routing), group theory, but also computer graphics and associated data structures, like octrees. We learned control theory, signal processing theory and audio and image processing. But also network protocols, TCP/IP, ARP, exponential backoff, Ethernet frames etc. Databases, normalization etc. Compression algorithms, cryptography, Reed-Solomon code and its use in CDs, similar codes in RAID. Public-key crypto theory with proofs but also its use in practice in SSL. Backups, differental and incremental, practical stuff like calculating with mean time between failures, etc. Understanding hard disks, like the plates, sectors etc to understand delays and better seeking algorithms. But also GPU architecture, programming GPUs through shaders, breaking down math problems in a way that maps well to CUDA etc (before the deep learning craze, but when GPGPU was a hot new term). Java, C++, UML. Machine learning, evolutionary algorithms, agent and voting systems.
We don't have a good vocabulary. Are the above things all CS? Or some are engineering? What does informatics even mean? Certainly a lot of the above is intimately tied to computers as physical objects with timings, latencies, voltages, not just to abstract Turing machines. And I wasn't raised to be ashamed of that or to find that dirty. Nor to be bitter about having learned about red-black trees or the proof of the five color theorem or Cauchy's integral theorem or the simplex method for linear programming or linear algebra or the conjugate gradient method etc. It's possible to have the right blend of the abstract and the concrete.
And how do you learn "problem solving" if not through actually working with things like the ones I listed? Why this distancing from concrete metal-and-wires computers as opposed the pure mathematical formalisms? Is it because it's seen too close to blue collar, wrenches-and-sweat-and-grease work? That the image of a scholar sitting in an armchair is nobler? You don't have to become a help desk technician or a person plugging in the Ethernet cables at data centers, just because you've studied the concrete technical aspects.
It sounds as if medical practice were low status and only biological research had prestige. Or if practicing law was too blue collar and only things like abstract constitutional law theory was something of high worth.