I think that CS should be taught in middle school in place of pre-algebra and algebra, and then condense algebra and algebra 2 into one course.
And don't try to teach it like the kids are theoretical mathematicians. You are not going to be teaching actual Computer Science, but some programming fundamentals. Yes some freakin' geniuses were able to figure out computation science back in the late 19th century, without computers, but those were freakin' geniuses. Your high school and middle school kids are not that. They have actual computers, make use of them. Show them some end results instead of some foundational theories.
My introductory CS class in university was doing an experiment where they were trying to introduce computer science while teaching minimal programming. The book was very boring. I couldn't get through a single page without falling asleep. The multiple naps-per-reading assignment made the reading assignments very long. When we went to sell the book back at the end of the semester we couldn't because the CS department realized that their experiment had failed. Two semesters later, I was trying to fall asleep and couldn't. I pulled out this book with the purpose of getting me to fall asleep and it didn't. Now that I had some programming experience under my belt I found the book to be fascinating, and very informative. I could see why the professors thought it was a good way to learn the basics without them being tied to a specific language. I suspect most people need some practice with some end products, before they are able to "get" most of why the theoretical stuff even matters.