What makes the Discrete Logarithm Problem hard? I am missing a crucial piece of the maths behind the DLP, and I'm hoping someone can give me a really dumbed down answer..

If  $h=g^x \bmod p$  and we're working in the group $Z^*_p$, why can I not find $x$ in linear time given I have $h, g, p$, and $Z^*_p$? I have at most $\operatorname{ord}(Z^*_p)$ iterations to run through? 

I can't see what aspect of the maths I'm obviously misunderstanding. Is it not linear to calculate $g^x \bmod p$ for some $x$? That's my only guess.
It is true that you have in the worst case $\operatorname{ord}(Z^*_p)$ values to test. However, the complexity of a problem is actually measured according to the size of the input of the problem in computer representation which is binary.
Here the inputs to our problem are h and p. These two are integers both of size $log_2(p)$ at most in computer binary representation. And the algorithm would take $\operatorname{ord}(Z^*_p) = p$ iterations. However, $p = 2^{log_2(p)}$, so we can clearly see that the number of iterations required is actually exponential to the size of our input of the problem. Which is why the discret logarithm problem is hard.
When you usually see complexities of the form $O(n)$ or $O(log(n))$, we actually assume that the size of our problem is $n$ in computer representation, without explicitely saying it.