The first thing that comes to mind as something you might find fascinating is Kolmogorov complexity; I certainly find it fascinating, and since you didn't mention it, I thought it might be worth mentioning.
That being said, a more general approach to answering this question might be based on the theory of languages and automata. Deterministic finite automata are O(n) string processors. That is, given a string of length n, they process the string in precisely n steps (a lot of this depends on precisely how you define deterministic finite automata; however, a DFA certainly does not require more steps). Nondeterministc finite automata recognize the same languages (sets of strings) as DFAs, and can be transformed to DFAs, but to simulate an NFA on a sequential, deterministic machine, you must typically explore a tree-like "search space" which can increase the complexity dramatically. The regular languages are not very "complex" in a computational sense, since we can determine whether a string is in a particular regular language in time proportional to the length of the string.
You can similarly look at other levels of the Chomsky hierarchy of languages - deterministic context-free, context-free (including nondeterministic context free languages, which cannot necessarily be recognized by deterministic pushdown automata), the context-sensitive languages, the recursive and recursively enumerable languages, and the undecidable languages.
Different automata differ primarily in their external storage; i.e., what external storage is necessary for the automata to correctly process languages of a certain type. Finite automata have no external storage; PDAs have a stack, and Turing machines have a tape. You could thus interpret complexity of a particular programming problem (which corresponds to a language) to be related to the amount or kind of storage required to recognize it. If you need no or a fixed, finite amount of storage to recognize all strings in a language, it's a regular language. If all you need is a stack, you have a context-free language. Etc.
In general, I wouldn't be surprised if languages higher in the Chomsky hierarchy (hence with higher complexity) also tend to have higher entropy in the information-theoretic sense. That being said, you could probably find lots of counterexamples to this idea, and I have no idea whether there's any merit to it at all.
Also, this might be better asked at the "theoretical cs" (cstheory) StackExchange.