If I am interested in specializing in theory of computation, should I be looking for a PhD program in CS or math? I took a Theory of Computation class years ago through my university's math department that I really enjoyed and found interesting. If I wanted to further pursue study/research/specialization with Theory of Computation what what kind of Ph.D program should I be looking for? Computer Science or Math. I am leaning towards Math grad school since I not inclined to take take classes about Database and OS design.

Has the prevalence of computer science programs in major universities during the past 30 years made the new researcher in the Theory of Computation normally a CS grad student or is it normal for pure math grad students specializing in theory of computation?
Generally speaking, in the US, the theorists will be in the computer science department, but it will not be hard to make arrangements for you to work with them as a student in the math PhD program.

Would you prefer to TA and eventually teach introductory programming courses, or calculus courses?  That's probably going to be the biggest difference (especially down the line after you graduate) between the two options.