I, myself, did not do computer science at university (I did civil engineering), and regret that a great deal. Not only does learning this stuff make you considerably more hire-able, it also enables solution of problems more sanely than a naive approach.

The real thing I feel that I miss is not being able to recognise where known algorithms/data structures could help out, something I'm working on fixing.