I'm surprised to see strong support for the MS in Stats. I'll make the argument for a MS in CS (which I'm finishing now).
First, and most importantly: any decent CS program will let you take electives. I'd suggest taking ML and statistics classes for yours; to that end, make sure your school has a decent statistics department!
I can say, with certainty, that smaller teams will not hire a stats/ML specialist. Small teams search for broad skill sets to maximize for productivity. If you haven't studied CS, you can use a MS in CS to develop the broad engineering/analytical skill set smaller teams desire.
Regarding "picking up computer science online," be careful not to confuse software engineering with computer science. As a data scientist, you need to understand how algorithms and advanced data structures (read: not just stacks and queues!) perform. You might need to think about whether your current problem is NP-hard. You will also need to reason about convergence rates. CS theory covers all of these topics.
Finally, studying scientific computing as part of a good CS program will prepare you for all sorts of real-world issues: writing well-factored code, performance issues, numerical precision issues, etc. You can definitely pick this up in a math program, though...
At NYU, "a few" is actually 8 of 12 required classes. This granted me enough flexibility to take the math classes (scientific computing, linear algebra, optimization, stochastic calculus) and ML classes (learning theory, graphical models, survey class with emphasis on deep learning, independent study) I felt would best prepare me for this type of work.
The core classes -- languages, algorithms, OS, a capstone -- are also relevant if you plan to code.
Also note that "statistical theory" comes at a price: 2 years of statistical theory means 0 years of formal CS or engineering training.
