Add things like decision trees (which you need to build something like a chatbot). In fact, a friend of mine from my freshman year (way back before everyone had computers in college) wrote a chatbot. I had never seen anything like it, and he let it loose on IRC. Was pretty cool back when things like rn and ftp were all there were on the net.
Regression isn't that hard. Heck, most advanced Calculus and further maths are way harder.
Neural networks aren't even that complicated, although tuning and understanding the output sure is. But that comes with time.
Markov Chains are basically advanced flowcharting. If they can teach PERT analysis to Business majors, then Markov should be easily understood.
Sure, there are some hardcore things, but the foundation is based on stuff many smart people should be able to learn in undergrad. Twenty years from now, when we are surrounded by "AI"-everything, we'll wish more schools did this. And I guarantee you'll wish your kids learned this in high school.
Yes, I am serious about that last comment. I have an 8 year old son, and I'm already working on teaching him Markov Chains using sports. Yes, it's super simple, but easy enough to teach him consequences of actions, without getting into nested probabilities.