After doing lots of the things mentioned here: get a good programmers editor (editplus for me), learn several programming languages (C++ and Lisp cover a whole spectrum of techniques), learn regexps (actually pretty simple, compared with other stuff, but amazingly powerful), learn about top-down parsers (that way you forget the idea that regexps can solve everything), I found the biggest help from an unexpected place:
This is not about learning calculus formulas or other stuff that is taught to engineers. That's not the mathematician mindset. This is about being able to think and write a correct proof for some theorem, sometimes grabbing ideas from the most unexpected places, or doing stuff that looks like a crazy workaround to the untrained mind. And advanced linear algebra course can be a great Mathematics intro.
After this, your programming mind literally grows bigger, by a huge amount. You can hold bigger and more complex pieces of code in your head, and it actually looks very simple. After some really hard Mathematics proofs, some complex algorithms look trivial to you in comparison.
However, there is a caveat: most Mathematics teachers will want you to be both the programmer, and the computer. You write the proof by hand, and perform all calculations of any application by hand, otherwise it has no merit. Most of them still don't understand the power of computers. In the same way, most programmers will disregard Mathematics as 'that bunch of calculus formulas with no direct relation to programming'. If you get the good bits from both worlds, you will be a better programmer than 99.99% of them all.