Given how effective stories and anecdotes are in convincing people, it really seems like the human brain is not wired to grasp these concepts easily.
also, probability theory vs statistics is an important distinction: prob theory is a nice clean mathematical subject, while statistics is almost the philosophy of applying probability theory to the world.
By the time I took my statistics class in undergrad math, coming from a similar background to you, they just sort of assumed you had a head for combinatorics and used that to develop everything else. I was a really good student in undergrad and statistics was my hardest class, I spent like 2x time on that class than any other class.
In grad school I took a class on complex system failure analysis and was quite apprehensive. My hope was that I could team up with a classmate to help with the math while I could work on the systems levels analysis. Turns out that because I understood systems really well, system failure offered me the intuition I needed to really understand statistics. I aced the class, published a moderately popular paper in distributed systems using what I learned, then went and took our graduate level statistics class widely known to be very difficult and aced it.
I think tacking statistical thinking on as an afterthought in curriculum is a huge mistake in the school system, especially so in the age of machine learning. I think for the average student statistical thinking is even more important than a lot of trigonometry.