I have been taught my whole life to solve math with an algorithm or method. My teachers in school trained us to identify patterns in equations and then use a method to solve it. No one has ever stopped to teach me the theory behind mathematics or help me to understand it on a deeper level. If I see a problem that I don't have a pattern already memorized for solving, I can't even begin to solve it.
I love math and really want to break-free from this sub-par public school teaching, but I am not sure where to start? Is it possible to relearn all of my mathematics experience in a more rigorous, actually higher-level critical thinking way? What can I do to develop true problem-solving skills so I can tackle much harder problems with free-thinking?
IMHO one of the most exciting things about mathematics is discovery. It's much more interesting to discover things for yourself than to have someone tell you. From what you have said in your question I think I can assume you will agree with me on this. BTW it doesn't matter if someone else has discovered the same thing before you did: it's still great to have worked something out for yourself.
So, although you have only been taught maths in a prescriptive way so far, you can still build on this. If you have a number of similar problems to solve, see if you can spot any common features in the results. Maybe you can find a short cut? Maybe you can find some unexpected feature of the results? Don't expect miracles to happen too quickly, but if you keep at it I'm sure you will get somewhere. Here are a couple of suggestions to start you off - as I have no idea of the maths level you are up to they may not be appropriate, but hopefully they will give you some ideas.
First suggestion. For $n=1,2,3,\ldots,10$, calculate the sum of the first $n$ cubes. That is, $$\displaylines{ 1^3\cr 1^3+2^3\cr 1^3+2^3+3^3\cr \vdots\cr 1^3+2^3+3^3+4^3+5^3+6^3+7^3+8^3+9^3+10^3\ .\cr}$$ Now look at your $10$ answers. Can you see anything special about these numbers? Do you think the pattern will continue? Can you prove that it will always be true?
Second suggestion. For $n=2,3,\ldots,10$, calculate the number $(n-1)!+1$. In case you haven't seen it, the exclamation mark denotes a factorial, for example $5!=5\times4\times3\times2\times1$. In other words, calculate $$1!+1\,,\quad2!+1\,,\quad3!+1\,,\quad4!+1\ ,\ldots,\quad9!+1\ .$$ Now divide these numbers by $2,3,4,5,\ldots,10$ respectively and write down the remainders. For example, in the third case we have $3!+1=7$ and if we divide by $4$ the remainder is $3$. Do you notice anything about these remainders? Can you prove it is always true?
BTW I would also definitely second the recommendation to Polya's book which was given in a comment.