This is also somewhat in reply to your elaboration in this comment. Just some data points:
In regards to this topic of proof, and more generally to the topic of formal science, I have found logic a very useful subject. For one, you can leverage your verbal reasoning ability, and begin by conceiving of it as a symbolization of natural language, which I find for myself and many others is far more convenient than, say, a formal science that requires more spatial reasoning or abstract pattern recognition. Later, the point that formal languages are languages in their own right is driven home, and you can do away with this conceptual bridge.
Logic also has helped me to conceive of formal problems as a continuum of difficulty of proof, rather than proofs and non-proofs. That is, when you read a math textbook, sometimes you are instructed to Solve, sometimes to Evaluate, sometimes to Graph; and then there is the dreaded Show That X or Prove That X! In a logic textbook, almost all exercises require a proof of validity, and you move up over time, deriving new inference rules from old, and moving onto metalogical theorems. Later returning to books about mathematical proof, I found things much less intimidating. I found that proof is not a realm forbidden to those lacking an innate ability to prove; you must work your way upwards as in all things.
Furthermore, in regards to this:
Even the math with simple foundations has surprising results with complicated proofs that require precise understanding.
In my opinion, very significant and complex results in logic are arrived at quite early in comparison to the significance of, and effort invested in, results in other fields of formal science.
And in regards to this:
I think this makes it all the more educational when a surprising result is proven, because there is less room for a beginner to wonder whether the result is an artifact of the funny formalish stuff.
I have found that in continuous mathematics I have walked away from proofs with a feeling best expressed as, "If you say so," as opposed to discrete mathematics and logic, where it's more like, "Why, of course!"
The social justice movement espouses the notion that people who are privileged are often unfairly judgmental of those who were less privileged. Until recently, what they said didn't resonate with me. I knew that I had major advantages out of virtue of having been born a white, middle class male. But I recently realized that there were other privileges that I hadn't acknowledged as having benefited enormously from. In particular, I had the unusual experience of growing up with a very intellectually curious father, which gave me a huge head start in intellectual development.
I used to get annoyed when LWers misread my posts in ways that they wouldn't have if they had been reading more carefully. I conceptualized such commenters as being undisciplined, and being unwilling to do the work necessary to maintain high epistemic standards. I now see that my reading was in many cases uncharitable, analogous to many of my teachers having misread my learning disability as reflecting laziness. Many of my readers have probably never had the opportunity to learn how to read really carefully.
How did I myself learn? I don't remember in detail, but the one factor that seems most significant is my study of the mathematical subject of real analysis. A number of strongest thinkers who I know characterized the experience as a turning point in their development as well. It's the subject where one goes through rigorous proofs of the theorems of calculus.
Consider the extreme value theorem:
The theorem may seem obvious, but almost no undergraduate math majors would be able to come up with a logically impeccable proof from scratch. This ties in with why I almost never try to present rigorous arguments. If it's not clear to you that it might be very difficult to construct a rigorous proof of the extreme value theorem, you'd probably benefit intellectually from more exposure to mathematical proof. The experience of seeing how difficult it can be to offer rigorous proofs of even relatively simple statements trains one to read very carefully, and not make any unwarranted assumptions.
If you've studied calculus, haven't yet had the experience of proving theorems from first principles beyond high school geometry, and would are interested, I would recommend:
The last of these books is great for developing a sense for how superficially plausible statements are often false.