What you got about the role of rote learning from your teachers is bad and appears not to be from teaching in the US.
The 'understanding' you explained you wanted want in math IS the right direction. The proper role for 'rote' learning is meager.
To get anything new, or even new to you, in math, first essentially have to guess it. For this you need some intuition, that is, some ways to guess. You should be free to take wild flights of intuition where only one in a million guesses is correct. Proofs, then, add discipline to your intuition. Slowly your intuition becomes more accurate.
E.g., given a guess, do some 'thought checks': So, check some extreme cases. Guess what some of the consequences might be and see of those, first-cut, seem to be true or false. Then will have guesses (1) very likely true, (2) very likely false, (3) don't much know yet. Once you narrow down to what you need, you will be well on your way to success.
Actually for anything new, the harder work is guessing it's true and being fairly sure, based mostly on intuition and your checks, it is. Then usually a proof is the less difficult work. That is, by the time you start a proof, you might have some quite good intuitive evidence that what you are trying to prove is true and, also, some good hints on how to prove it.
For more, read the now famous comment by A. Wiles on how he wanders in dark rooms in an old mansion, bumps into furniture, slowly figures out where everything is, finally finds the light switch, then clearly sees everything in the room, and then starts on another dark room. Practiced intuition provides the guesses, and proofs provide the correctness.
What I am saying here about guessing, Wiles, etc. is good for research, e.g., your Ph.D., and some of the more difficult text book exercises. Mostly in the exercises can do well enough with less than a million wild guesses!
Yes, there is some 'sense' to at least the 'analysis' (i.e., calculus and beyond) part of math. E.g., 'half' of calculus is finding areas under curves. Okay, what curves have properties sufficient actually to HAVE area well defined in this sense? Okay, the now classic answer is that the curve has to be 'continuous'. So, when you learn about continuous curves, you are learning about the classic hypothesis that makes area under the curve well defined.
Okay, why? Well, that's because are trying to find the area under the curve over a 'closed' interval such as all the numbers x so that 0 <= x <= 1, that is, the interval [0,1]. Okay.
What's so great about such a close interval? Uh, it's 'compact' so that any infinite subset has a limit point -- that is, if take infinitely many points, they MUST bunch up at least somewhere. We know that [0,1] is compact because it is closed and bounded. Also, a continuous curve on a compact set is 'uniformly' continuous, that is, is highly restricted in how fast it can 'wiggle'. So, it has to be somewhat 'well behaved'. Also, that curve has to be bounded -- can't run off to infinity, either positive or negative. Also the curve has to actually have a largest value and a smallest value.
Then, consider all such continuous curves on [0,1]: Let the 'distance' between any two be the absolute value of their maximum difference, which we now know has to exist. All those curves form an infinite dimensional vector space, and that distance is a 'norm'. Next, if a sequence of such curves appear to converge, then they really do, that is, that vector space is 'complete' (much as you learned for the real numbers) in that vector space and, thus, is a Banach space. Now you have a nice list of surprising Banach space properties -- Hahn-Banach, open mapping, closed graph, uniform boundedness.
Now you have some of the high points, intuitively, of Baby Rudin and some what makes 'sense' there.
I very much disagree with most of the advice in this thread: E.g., I read Bell's 'Men of Mathematics' and CANNOT recommend that book: (1) It won't give you the understanding you said, appropriately, you wanted. (2) It's a BIG distraction, misleading, even dangerous, from anything like math now. Polya is okay but a bit off the track. Maybe read Polya about half way through your college level studies.
Instead, for what you want, the usual courses are FINE and are:
HIGH SCHOOL:
first year algebra
plane geometry (with all the emphasis on proofs)
second year algebra
trigonometry (with all the emphasis on proving the identities)
solid geometry (with all the emphasis on proofs), optional but good if you can get it.
COLLEGE:
freshman and sophomore calculus from any of the famous books, e.g., Protter and Morrey, Thomas. Here seek to get some of the understanding you want via pictures and applications to physical science and engineering.
abstract algebra -- emphasis on proofs and a really good start on the understanding you want.
linear algebra -- emphasis on proofs.
Baby Rudin (W. Rudin, 'Principles of Mathematical Analysis') -- calculus with the proofs.
ordinary differential equations -- with Baby Rudin and linear algebra, can do well with nearly all the proofs. I like Coddington's book. Then have some fun with deterministic optimal control, A/C circuit theory, and more.
advanced calculus -- various applied topics in 'analysis', often without the proofs, e.g., Hildebrand's book long popular at MIT.
BIG Note: One of the most important applications of calculus in several variables is to Maxwell's equations. For that, you need Stokes' theorem in 1, 2, and 3 dimensions. For that, I STRONGLY recommend that you get an appropriate, OLD treatment. The best I know of is
Tom M. Apostol, 'Mathematical Analysis: A Modern Approach to Advanced Calculus', Addison-Wesley, Reading, Massachusetts, 1957.
He has a more recent book where he left out the good stuff; f'get his more recent book.
What you want from that old book is only about 30 pages. I got the whole book used -- no, I won't sell it! So, find the book in a library and make copies of the pages. Then can cover those pages in one very pleasant evening. Then will have quite well the calculus of several variables you need, and that nearly all of the physical science community STILL uses, for Maxwell's equations and more. For the math stuff with exterior algebra, etc., that's mostly for later and mostly for modern approaches to relativity theory.
Uh, Stokes' theorem done that way is just some simple pictures and a simple application of the fundamental theorem of calculus you learned in freshman calculus and proved in very fine detail in Baby Rudin.
By then you should have all you want and more.
A high school plane geometry course with all the emphasis on proofs is one of the best starts for the understanding you want.
In the books where the emphasis is on proofs, nearly all the exercises are proofs. The easy exercises you should be able to do easily enough, and as you work on the more difficult exercises you will get good at proofs. By the time you can write a good proof of, in any separable metric space, each closed set is the union of a perfect set and a set that is at most countable, you will be well on your way.
Generally, as you start to write proofs, you should have at least a semester where a good mathematician reads and corrects your proofs. The usual place for this help is in the course on abstract algebra.