If I am interested in specializing in theory of computation, should I be looking for a PhD program in CS or math?
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.