One thing that's nice about k-means is that it can quite literally be grasped intuitively by, say, a 10 year old. k-nearest neighbors is similarly graspable. I think these are wonderful techniques to introduce kids to data science without having to get into the math. Obviously you're going to have to abstract away high-dimensionality and a lot of the underlying math of "how" -- but that's ok!

I'm not sure I've found either to be massively useful on real-world data, but that's OK too!