What 'procedural' habits to break when teaching 'functional' programming?
I undertook this study myself about a year ago. I started working through the Programming Languages MOOCs on Coursera (Part A Part B Part C), which are based on a UW course of the same name.

I didn't really know what I was getting into, but it sounded interesting. Before I knew it, I was learning a radically different approach to programming first with SML and now with Racket (Ruby is up next). 

Here are some of the key ideas that were a major departure from my having programmed in C and Python:


Avoid mutation. Over and over again the professor emphasizes why mutation is a bad thing (or at least potentially problematic). From the world of C where I learned about declaring and updating variables almost immediately, this forced me to think differently about the information my programs contained and processed.
Don't call them variables. As a continuation of the above, they aren't variables (because after all they shouldn't vary because they don't mutate); rather, call them "value bindings." Moreover, these value bindings exist in an environment. This latter idea is essential (and has only recently sunk in) for understanding function closures.
Think recursively. Of the 3+ assignments I've completed for Part A and Part B, thinking recursively has been an essential component for creating elegant, efficient solutions. Indeed, in some cases it's been the only way to solve a problem thanks to the goal of avoiding mutation. This is not to say that recursion doesn't exist in other languages (because it obviously does), but it's been a more fundamental element to the design of solutions using functional programming languages.


Those are my big three; I'm sure there are more. Obviously understanding anonymous functions, higher-order functions, first-class functions, and all that comes with them (e.g. currying) is what functional programming entails. However, this content wasn't a "rewiring of old habits" in the same way that the above points were.

For what it's worth, I appreciate what C has taught me about what happens on a lower level, but I think studying a functional language qua an approach to programming has made me an overall better programmer.