I don't think that you can appreciate this stuff until you actually have the mechanical background in math. Unlike most subjects in K-12, you can't BS math. You're right or wrong. There's no subjectivity in evaluation, and no opportunity for lazy students like me to BS a tired teacher with flowery prose that doesn't say much. Why not make math accessible in easier or more practical ways? My trigonometry teacher walke…
Mathematicians do (and students should) focus on proofs over computations, and there is an extreme amount of subjectivity there. If you produce a false proof, it can nevertheless be beautiful and yield fantastic insights. Likewise, a correct proof can be unsatisfying and ugly. Your goal then is to revise it (or completely rewrite it) to make it more beautiful and insightful.
Here is an example: the 7 Bridges of Konigsberg problem is one of the most famous (solved) problems in all of mathematics. One can easily give a proof by exhaustion, but that is wholly unsatisfying and perhaps the ugliest possible proof. A much better proof involves some insight into graph theory, and a satisfying and elegant proof would give you a characterization of these kinds of trails in graphs.
You don't need a mechanical background to start trying to solve such puzzles (I know because I've taught it that way), and you don't need any mathematical background to appreciate the very elementary proof. But as you let students flounder with puzzles like these, you can slowly introduce technical matter. The point is that it has a context they care about (people like working on puzzles!).