Computer science consists of a large number of things, theory of computation is part of it. But so are algorithms and data structures.
Practically speaking, the latter (algorithms and data structures) are the most accessible, and allow you to explore the former. Even if we think people should be taught how to express these concepts with a pseudocode, they're still learning to program (in a vague sense). But they can't explore the ideas of CS, outside of a formal approach if they don't program (pseudocode or actual code).
And the formal approach is not understandable (or as easily understandable) without a practical experience with the topic. Do you honestly believe that we should teach students category theory and abstract algebra before we teach them high school algebra? Or perhaps high school algebra before arithmetic? If they have no number sense, they won't be very effective in high school algebra. If they have no sense of the structure of algebra, they'll have a hard time developing an intuition for the more abstract algebra and math concepts.
The same is true for CS. I can sit down and teach someone the hierarchy of computational mechanisms (finite state machines, pushdown automata, Turing machines). But what good is that if they don't understand what those machines actually express? Understanding that regular expressions (not regex) are used to tokenize text, and that PDAs are used to parse text is a great practical introduction to those concepts and provides them with an intuition that they can then use to generalize those machine models to other structures.
So pick a point to start, and work up. Don't start at the formal level and expect it to be effective (unless the students already have a sufficiently advanced background, like a senior university math major could probably start with those machine models and work towards their applications, rather than the reverse).