Generally speaking, a function $f()$ is linear if $f(x+y) = f(x)+f(y)$ and $f(ax) = af(x)$.
The AES S-Box, which is a specific, predefined (key-independent) lookup table, doesn't satisfy these properties. You can do a quick verfication by picking two values $x,y \in GF(2^8)$ and verifying that $S(x+y) \neq S(x)+S(y)$ (where the addition operation is done in the field $GF(2^8)$, and is thus essentially the XOR operation). But the S-Box not being fully linear is not enough. It's very bad if it's just somewhat linear, in the following sense. There are various ways to define it. One of them is the Linear Property of the S-box, $LP(S) = \max_{a,b} (Pr_x(a(S(x)) == b(x)) - \frac{1}{2})^2$ which has to be low. It measures the existence of two linear functionals $a(),b()$ which tend to agree (correlate) or disagree on the input and output of the S-box.
If you were to calculate $LP(S)$ you would find that it is considerably lower than for a random lookup table ("the maximum input-output correlation amplitude must be as small as possible").
As for difference propagation, a similar property exists $DP(S) = \max_{a,b\neq0} (Pr_x(S(x)\oplus a == S(x \oplus b)))$, which measures the existence of two differences (deltas) $a,b \neq 0$ which propagate through the S-box. Again this has to be minimal, and if you were to calculate $DP(S)$ you would find it is indeed lower than for a random lookup table.
MixColumns offers linearity because it is defined as a linear mathematical operation, not because it is deterministic (the S-Box is also deterministic, but not linear...).
