Efficiently computable by a "simple" algorithm?
Elaborating on my comment as suggested by OP:

Let us start by giving definitions to the two definitions for program complexity as suggested by the other commenters and me.

Definition (Kolmogorov complexity of $L$): Let $L$ be some language. We define the Kolmogorov complexity $K(L)$ of $L$ to be the (description) length of the smallest program which decides $L$ (using some fixed programming language) or $\infty$ if no such program exists.

Definition (State complexity of $L$): Let $L$ be some language. We define the state complexity $S(L)$ of $L$ to be the minimal number of states a TM which decides $L$ needs to have or $\infty$ if no such TM exists.

The first observation we make is that there are only finitely many programs of length $n$ (and the same holds for Turing machines if we fix the alphabets and state names). It follows that any infinite class $\mathcal C$ of languages and any $m \in \mathbb N$, there is some language in $\mathcal C$ which has a Kolmorogov complexity which is at least $m$ (and the same holds for state complexity). 

Indeed, this means that even problems which can be decided in constant time can have an arbitrarily large program complexity, which makes me pessimistic about the existence of results that imply that a large program complexity incurs a large runtime complexity. What about the converse statement?

The same argument from above yields directly that if we have two (infinite) decidable complexity classes $\mathcal{C}_1$ and $\mathcal{C}_2$, then for any $L_1 \in \mathcal{C}_1$ there must exist some $L_2 \in \mathcal{C}_2$ with $K(L_2) &gt; K(L_1)$ (and the same result holds for state complexity) as $K(L_1)$ is finite (by decidability) and he program complexity for any infinite complexity class is unbounded. Even stronger, it follows that there exist infinitely many such $L_2$ and the difference in program complexity can be arbitrarily large (again by the first observation). In particular, one can deduce that for any decidable language, there exist infinitely many languages with (arbitrarily) larger program complexity but constant time complexity.