[minkowski]

In my (admittedly PL-influenced) view the primary concepts in programming are:

1) Compositionality - primarily via functions which implement substitution, but also composition of larger program units, e.g. via (ML-style) modules.

2) Recursion and induction -- sure, imperative languages make recursive solutions impractical, but ultimately most data structures (including programs) are defined inductively and algorithms on them are most clearly defined recursively.

3) Abstraction vs. representation (e.g. via existentials/modules, not necessarily or even primarily via OO).

I don't think these things are particularly complicated (although the proper semantics for modules is) but can't be learned overnight.