Concordo e discordo de você.
Também sou aluno de ciência da computação em universidade federal (a um semestre de finalizar o curso finalmente) e vejo qua a grande maioria da galera de programação que entra no mercado não sabe absolutamente nada sobre sistemas operacionais, estruturas de dados, redes, como a memória é estruturada, o quão eficiente é um algoritmo e quais problemas são possíveis de se resolver com computação e, sabendo quais problemas são esses e que estratégias temos para alcançar uma solução minimanete viável para eles. Para quem faz ciencia da computação em uma boa universidade, tudo isso se torna trivial logo no começo da carreira, por isso temos essa impressão.

Mas precisamos separar um pouco saber computação de saber programação.
A grande maioria das empresas precisa que você saiba programação, coisa que em um curso de faculdade você já aprende logo no primeiro ano (muitas vezes já no primeiro semestre) e saber computação é uma habilidade que não é tão necessária. Acho que para esse caso, a barreira de entrada deve ser baixa mesmo, dar oportunidade pro pessoal entrar em um mercado que realmente está precisando de gente.

Para os casos onde precisamos saber computação de fato e a progrmação se torna só mais uma ferramenta para alcançar um objetivo, ai concordo plenamente com você, o ensino precisa ser completo e árduo, com muito esforço e uma alta cobrança porque não é uma coisa fácil de se aprender e não é nem um pouco simples para se fazer vista grossa na hora de ensinar.