What is the purpose of a proof? You may think that it's intended to solve a problem, but that's really only half the point. A good proof is one that communicates your solution to other people.
Mathematical writing is hard to learn well under the best of circumstances, but if you don't have someone else giving you feedback on whether they understand what you're writing, it's absolutely impossible. You need to have a mentor or at least an editor at some point. That's not impossible to find outside of the university system, but it's very difficult.
(This is the single biggest reason why MOOCs for higher math haven't taken off. There are a lot of people who'd love to communicate something about the field that they've dedicated their lives to, but the feedback system just doesn't scale. If anyone can figure out how to fix that, it'll be a game changer.)
So the first thing you have to do is to figure out what you can reasonably expect to get out of this process. You can learn the definitions and theorems of higher math, and that might be enough, but you're never going to develop an intuition for them without understanding how to produce proofs on your own. And don't fool yourself into thinking that you can evaluate your own proofs. It just doesn't work.
If all of that doesn't have you turned off, then here are some ideas on what to do.
A university level math curriculum is split into roughly three components:
* Lower level classes that focus on basic definitions and calculations;
* Mid level classes that teach some basic theorem-proving skills in subjects that are useful for people in other quantitative fields;
* Upper level classes that offer serious practice in theorem-proving as well as the core ideas of mathematics.
You don't generally have to do classes in any particular order, but you do have to master the skills of each level before you go on to the next one.
To begin, you must be very comfortable with the contents of a high school math curriculum. Serge Lang's book on basic mathematics is a great refresher if you're not, or you can use any of the various popular study guides (Schaum's, Barron's, etc.).
At the first level, you have calculus. This is generally split into three semesters, with the first dedicated to limits and derivatives of single-variable functions, one dedicated to integrals of single-variable functions as well as sequences and series, and the last dedicated to derivatives and integrals of multivariate functions. There are plenty of very expensive books with glossy page and many color pictures and few ideas, but if you want a serious introduction, look at Peter Lax's books on calculus.
At the second level you'll almost always find introductions to differential equations and linear algebra. Differential equations have historically been the workhorse of applied mathematics and you really need to have some familiarity with them, but I've never seen a book on the topic that I liked. I probably won't be satisfied by anything at this level, though, so look around and see if you can at least find something inexpensive.
Linear algebra is a more recent topic (with many of its key ideas actually originating in the 20th century), but it's probably actually more important now. Gilbert Strang's books are popular and are worth reading for a first look, but you really can't regard them as a serious introduction to the mathematical side of the topic. Axler is probably the best book in that regard, but it's best taken on a second pass.
I think that probability should be regarded as a core class at this level. I don't think that's a fringe view, but it's not as universal as I'd like. I learned from Pitman's book, and I think it's as good as any to start with.
You can also take classes on complex variables or "discrete math" here. I don't know what a good textbook for complex variables is--maybe Saff & Snider?--but I'm sure there are recommendations out there. Needham's "Visual Complex Analysis" is a fantastic book, but maybe not really suitable for a very first introduction. As for "discrete math" (a jumble of topics from logic, combinatorics and number theory), find the cheapest book you can get that has decent reviews on Amazon.
At the third level, there are three main topics: analysis, algebra and topology/geometry. You can think of these as the three main viewpoints in higher math, and other topics being populated by people who primarily look at things with the tools of one of those three topics.
Analysis starts out as the theory behind calculus. In a first course, you'll revisit a lot of what you saw in single-variable calculus, but you'll learn why it's true rather than just how to use it. For a single semester undergraduate course, Ken Binmore's book is probably the gentlest introduction.
Modern geometry is related to what you studied in high school, but with a few more centuries of development. It also doesn't get a lot of coverage at the undergraduate level, which is highly unfortunate. Stillwell's "The Four Pillars of Geometry" is a wonderful book and completely accessible.
Algebra is a bit difficult to explain without getting into the weeds. Pinter's "A Book of Abstract Algebra" is very good at motivating the topic and explaining the basics, which is the best you can hope for in an introductory textbook.
Beyond that but still at the undergraduate level, you can get electives in combinatorics (use Brualdi), number theory (?), logic (?) and some applied topics as well. Looking through the course offerings of various math departments will help you to fill in what the other possibilities are.