All the other basic requirements of a university education are filled through entry level classes - credit-fillers that students have to take in order to graduate. This structure works out well for everyone: the university ensures that students are getting a well-rounded education (as opposed to a trade-school degree) and maintains its reputation and the value of its product.
The only classes that students can take to demonstrate an ability in computational thinking are CS classes. Entry level CS classes, like those in the other engineering disciplines, are not like entry level classes in non-engineering disciplines. Most students that take ARCH 101 and LIT 101 are not taking them because they are interested in pursuing the major, they take them because they were the best-sounding classes that help them to fill their credit requirements. In doing so, they end up with a well-rounded education. In contrast, most students that take EE 101 are trying out for EE as a major.
CS entry level classes traditionally fell into the latter category. Demand has resulted in students treating them as part of the former.
The best thing a university could do is to figure out what skills that these employers are all demanding and offer entry-level classes to fill the need. Structure them to work with large numbers of students, just like all the other 100 and 200 level classes that everyone takes.
Here's the key part: advertise these classes relentlessly, to students and employers. Talk about how the university has seen the demand for these skills and has shifted to focus on them. Become known as a university where every student can get these skills as a part of their education, regardless of major, and most choose to.
Potential students will be thrilled at the prospect of a university where they can get a bankable education without having to commit to CS as a major. Strain on the CS major will go down and prestige will increase - if every student is getting the kinds of CS skills that employers require, then the ones that enter the major must be the hardest of the hardcore.