Earlier quoted context omitted.
I think the solution is to have, as is the case in math/physics, an honors intro CS sequence compared to the regular intro CS class. The latter would be the recommendation for all non-CS majors, and the former would be for CS majors. I've always thought that those who are focusing on more vocational training should not be in what is called the CS program, maybe there are other majors called "software development" or…
Similarly for math. I had to take a linear algebra class as a math major that was mostly populated by engineering majors and it was painful (given that they were allergic to proofs).
I acknowledge high schools are notorious in omitting the introduction to proof techniques but it’s a one time hurdle and you end up with a good stuff in your toolbox.