Of course everybody has their own learning style. Here are some general suggestions.
Find a teacher. It is hard to learn mathematics on your own until you have reached a certain level of mathematical sophistication; nobody is there to tell you what is important and what is unimportant. Take courses at a university; as Agusti Roig mentioned, video lectures on MIT's OpenCourseWare are a good cheap alternative.
Read as much mathematics as you possibly can, from as many sources as you possibly can. This is not limited to textbooks but extends to popular math books, blogs, expository papers, MO, math.SE... doing this will get you used to not understanding things, which is important. It will also expose you to many fascinating ideas that will fire up your curiosity enough for you to look at the material more seriously. As Ravi Vakil says:
...mathematics is so rich and infinite that it is impossible to learn it systematically, and if you wait to master one topic before moving on to the next, you'll never get anywhere. Instead, you'll have tendrils of knowledge extending far from your comfort zone. Then you can later backfill from these tendrils, and extend your comfort zone; this is much easier to do than learning "forwards".
A specific way in learning backwards is easier than learning forwards is that instead of reading the proof of a theorem in a book, you might hear about a theorem without proof, but remember that someone on a blog said something vague about a crucial step, then gradually learn enough material that suddenly you can work out the proof independently. I have done this a handful of times, and it is quite satisfying. For example, the theorem I proved in this blog post is classical and extremely well-known, but I had never seen a proof of it. I juggled around some ideas for about half a year until I figured out how to prove Lemma 6 (which I saw in a paper somewhere, again without proof), and I wrote down a proof. Later I read a proof in an actual book, and although the second half of the proof was similar, it did not use Lemma 6. I have yet to see a proof of Lemma 6 in print, although I am sure it is also well-known.
This might sound like more work. But guess how well I remember this theorem and its proof now!
Do as much mathematics as you possibly can. This is not limited to textbook exercises but includes competition problems, finding alternate proofs of theorems, working out concrete examples of abstract theorems, etc. I try to do this as much as I can on my blog; it keeps me sharp and is also, at least for me, much more fun than reading a textbook, which I can't do for long periods of time. This is also why I post here so often.
Question everything. There are a few aspects to this. If something is unclear or unmotivated to you, ask yourself exactly where it becomes unclear or unmotivated. Find someone to explain it to you (for example, on math.SE!). Read a blog post about it. Write a blog post about it! Ask yourself how things generalize and how they connect to other things you know. (Again, math.SE is good for this.) The worst thing you can do is to accept what a textbook tells you as the Word of God.
Finally, teach as much mathematics as you possibly can. This is the other purpose of my blog, and is an amazing test of how well you understand something. You would be surprised how much you can learn about something by teaching it.
Sounds like you are in for quite an adventure.
Mathematics is a huge, vast forest of knowledge. The choice of foundations to master and the path towards advanced topics depends to a great deal on precisely what it is that interests you. It sounds like you are not sure yourself what precisely it is that interests you so here goes some general advise to self-learning mathematics, assuming that you are interesting in understanding it all and not just memorize some techniques.
Disclaimer: These are only my humble opinions.
The language: Mathematics is written (mostly) in English augmented by set theory and/or category theory. The former is indispensable while the latter is only highly recommended. There are plenty of books on naive set theory (since you certainly don't want to start with formal set theory until you become seriously interested in logic and set theory). Halmos' "Naive Set Theory" is old but very very good. There are also various texts on category theory (including notes on category theory for CS which you might prefer). Category theory might be hard to digest so you might want to take it slow with categories and read on it while you are reading other things.
It is safe to assume that for the topics that seem to interest you you will certainly need a good dose of analysis. To save time and if you are up to a bit of abstractness look for textbooks that talk also about general metric spaces (e.g., Larussens' "Lectures on Analysis").
Linear algebra is also certainly going to be required. The book "Linear Algebra Done Wrong", despite its name, is a good text.
You should probably set this for yourself as a first goal. As you won't have plenty of time to put into it it might take you a good year to reach that milestone, if not longer. Once that is done you can think about how to proceed.
One thing to remember is that even if it will take you a very long time to get where you want to get to, the things you will learn on the way are very likely to assist you not so much on their own right but rather due to the analytic skills you will develop when working on challenging mathematics problems. Good luck!
Best Answer
In my opinion, you have answered your own question when you stated:
Good mathematical intuition is the result of hands-on practice, not its substitute. Yes, you must also keep the big picture in mind, but if you really want to learn this stuff, you have to get your hands dirty. Especially with proofs.
(I also agree with @skullpatrol's answer.)