My question is, do you think that an MS in CS will actually cover the interesting theoretical stuff, or is it likely to be more practical "here's how to get a decent job in IT" kind of thing? Obviously this varies, but honestly more than one or two of those kind of classes would turn me off of the degree. Something like maximally efficient handing of n threads over m processors? Yes, please.
Any comments or anything? I know so little about it that I'm really not sure what I don't know. It just sounds (potentially) interesting.
You are asking hypothetical questions about CS graduate degrees. Though, any useful answers will be dependent on your specific CS program.
While it is good that you have talked to the CS department head, department heads change. Whether or not the new department head will share the same philosophy as the old one is unknown.
Some issues.
One
For most graduate degrees, the faculty, and their research interests, are much more relevant than they are for an undergraduate degree.
Are you familiar the recent papers that your department head has published?
Google Scholar can be a handy reference here. Have you searched the publications of the other CS faculty?
Do their research areas overlap with your interests?
Two
There are several broad types of masters level degrees. In general, a STEM masters with have either a research or a professional orientation. As you would expect, a research orientation would be designed to prepare a student to earn a Ph.D. In contrast, a professional orientation would be designed to prepare a student for employment.
What is the orientation of the program that you are considering?
Three
Since you don't have a CS undergraduate degree, you will likely have to take 'levelling' undergraduate classes.
Do you have anything in writing that tells you how many undergraduate course that you will need to take before you can be admitted to the CS masters program? Do you know when they are offered and what their prereqs are?
Four
Since you have already earned an undergraduate degree, will you company pay for you to take these undergraduate levelling courses?
Five
Are you aware of the Ph.D glut? Are you prepared to do several years of academic work to prepare yourself for a $40,000 a year postdoc? See:
More Ph.Ds than ever
Nature on the Ph.D Glut
or
"Earning a Ph.D. may pay off if your goal is status, although I don't understand why anyone regards a Ph.D. as a status symbol that is worth giving up five to ten years of your earning power in your youth, when every dime saved can multiply because of compounding. If the public understood the economics of earning a Ph.D., people would think "naïve economic loser" whenever they hear "Ph.D."
Best of luck,
Uno