My Background: Current Undergraduate in CS and I recently added Mathematics
The most difficult part for a person who hasn't done a lot of math to become a person who does a lot of math is to read and understand rigorous proofs. You will encounter countless difficult proofs in any mathematical topic you try to study. Read a few books on mathematical thinking and proof techniques before/during/after reading any other dense math book.
Like you, I realize the value of having a mathematical mindset and want to have a deep understanding. When I added math as a major, I had a very hard time jumping from computational courses (typical math courses, geared towards any major) to theoretical and conceptual courses (proof-based courses that use all the fun and interesting math books everyone has linked here). These books helped:
<3 this is a great book, obvi since its george polya