Why do non-Newtonian fluids go hard when having a sudden force exerted on them? You can dip your hands into a bowl of non-Newtonian fluid but if you are to punch it, it goes hard all of a sudden and is more like a solid than anything else. 
What is it about a non-Newtonian fluid that makes it go hard when having a force suddenly exerted on it?
How does it go from being more like a liquid to a solid in such a short amount of time?
Does it change its state as soon as the force has made contact with it?
 A: A quick comment on your terminology. The description "non-Newtonian" just means the stress/flow rate graph is not linear i.e. there isn't a single constant viscosity coefficient. The fluid you describe is what we colloid scientists call "dilatant", and it is certainly non-Newtonian. However there are lots of other non-Newtonian fluids such as tomato ketchup and shampoo that behave in different ways. See Are there good home experiments to get a feel for the behavior of yield-stress liquids? for a related question.
Anyhow, kleingordon has explained why the dilatant effect occurs, but let me try a slightly different approach to the explanation.
Oobleck is a suspension of solid (starch) particles in water. Suppose you had a very dilute suspension i.e. lots of water and a little starch. In this case the spacing between the starch grains is large so the grains can flow around without hitting each other, and the suspension just behaves like water. As you increase the amount of starch the spacing between the grains decreases, until at some point the spacing between the grains becomes less than the size of a grain. At this point, when you try apply a large force to suspension the starch grains bump into each other and lock together to form a framework. The water in the suspension now has to flow through the small pores in the starch grain "framework" and this requires a lot of force. Hence you can stand on the suspension for a moment. If the apply a small force the water/starch grains move slowly and this gives time for the starch grains to slide around between each other so they will flow. This is why the chap in the white shirt could run on the oobleck, but when he stood still he gradually sank.
A: I can address one class of non-Newtonian fluids consisting of solid particles dispersed in a liquid medium, such as the cornstarch and water mixture commonly called "oobleck." In more scientific language, I am talking about concentrated colloidal suspensions of particles. Here is an image of oobleck, taken from Dounas-Frazer et al 2012.

These fluids tend to be shear-thickening, as you describe. Their viscosity increases substantially once the fluid velocity increases above a critical value. This tends to make them stiffen in response to impacts, which allows for fun activities such as running across the fluid surface (watch http://youtu.be/yHlAcASsf6U and related videos. The Faraday waves are also especially engrossing).
Here's how the shear-thickening comes about: Imagine a velocity gradient in the fluid. Then grains in one layer of the fluid will have to "roll over" particles in another layer of the fluid, colliding with each other as they do so. The steeper the velocity gradient, the more the fluid will tend to "dilate" in the direction normal to the gradient. But once the dilation effect gets sufficiently large, the water's surface tension provides a confining force that resists further dilation. This makes it much harder to maintain the velocity gradient and so the viscosity goes way up. (This explanation is based on the discussion in Fall et al 2007). 
A: A Newtonian fluid is by definition one where the shear stress $\sigma(t)$ at time $t$ is linearly proportional to the strain rate $\dot{\gamma}(t)$ at the same time, i.e.,
$$\sigma(t) = \eta \dot{\gamma}(t)$$
where $\eta$ is the fluid viscosity. Any fluid that does not obey this behavior is a Non-Newtonian fluid. 
A class of non-Newtonian fluids are viscoelastic. This means that the fluid displays both elastic (solid-like) and viscous (liquid-like) behavior. If you further look at the regime where the stresses and strain rates are "small", then you get a linear viscoelastic material. A simple model of linear viscoelasticity is the Maxwell model
$$\frac{d\sigma(t)}{dt} = -\frac{\sigma(t)}{\tau} + \frac{\eta}{\tau} \dot{\gamma}(t)$$
where $\tau$ is the stress relaxation time. For $t\gg\tau$, we get $\sigma(t) \sim \eta \dot{\gamma}(t)$ whereas for $t\ll\tau$, we find that the stress is proportional to the strain, i.e., $\sigma(t) \sim E \, \gamma(t)$ where $E=\eta/\tau$ is an elastic modulus.
This means that if you probe the material at short times, like punching it, it behaves like an elastic solid. However on longer timescales, the material flows like a liquid in response to an applied stress, like dipping your hands in slowly. Do also read about (and, if possible, play with) the silly putty.
In principle, all materials display viscoelastic behavior. It is the value of $\tau$ which governs the kind of response you see in a certain time. For water $\tau \sim 10^{-12} s$ whereas for glass  $\tau \sim 10^{32}$ years. For non-Newtonian fluids, like the silly putty, $\tau$ is commensurate with our attention span and so it will bounce as well as flow before human patience runs out.
