Why does pressure increase with water depth? Let's say I took a tiny metal sphere that when put under water has the surface area to allow, at any point in time, to be surrounded by up to 1000 water molecules. Now lets say we put this sphere first in shallow water and then in the Mariana Trench. Obviously, the sphere would feel much more pressure in the deep water! But why is that? Let's look at the formula's:
For the pressure from the 1000 water moleculse:$$P=1000*\frac{F_{molecule(H2O)}}{A_{sphere}}$$
Assuming the collisions of the water molecules with the sphere are perfectly elastic and are always in the same direction and happen in the same period of time:
$$P=1000*\frac{2m_{molecule(H2O)}*v_{molecule(H2O)}}{A_{sphere}*\Delta t}$$
So the only variable here is the velocity of the water molecules. But we know that deep water is colder than shallow water so the kinetic energy, and thus velocity, of the water molecules in the mariana trench is lower and so it doesn't make much sense that the pressure would be higher.
P.S. To be explicit. My logic here is that the only things capable of DOING the force (to cause pressure) are the water molecules directly in contact with the sphere. That is where an exchange of energy would be happening.
 A: Pressure is higher because at deep water you have so much more water on top pushing down on you because of gravity.
A: Think of water molecules at a certain horizontal level.  
They have a weight and forces acting on them from the water molecules above both of which must be balanced by an equal upward force from the water molecules below.  
Those water molecules below exert a larger force on the horizontal layer of water molecules because their average separation is slightly less that the average separation between the molecules above the horizontal layer of water molecules.
So think about the interactive forces between the water molecules rather than worry about the average separation between the molecules.
The temperature being lower would mean that the average separation of the water molecules will be less but the idea of balancing forces still stands.
A: An ideal liquid has uniform pressure. Water is not an ideal liquid.
Water does compress. We just mostly ignore it because it doesn't compress enough to matter most of the time. A kilometer deep, water molecules are a tiny bit closer together than closer to the surface, and given that the force between the molecules is inversely proportional to the square of distance, a tiny difference in density can mean a huge difference in pressure.
You're considering water molecules randomly impacting the steel ball. But that's really more how gases work, not liquids. Liquids are condensed matter, just like solids - intermolecular forces are what prevents their compression, not statistics. The molecules that hit the steel ball don't bounce away into oblivion, they bounce away from the other water molecules and back to the steel ball, moving (mostly) back and forth. In a simplified scenario, you can assume that while the individual molecules wiggle around, they don't really move freely as in a gas. Each molecule interacts with the molecules around itself, unlike in an ideal gas as long as the liquid is static enough (e.g. uniform temperature, no currents etc.). Liquids don't obey the ideal gas law, obviously - the relationship between pressure and density is not linear. Which is a good thing, really, otherwise we wouldn't be able to walk :P 
If you want a more realistic depiction of your scenario, consider that there's a tiny bit more molecules around the sphere as you increase pressure, because the mean distance between the molecules is a tiny bit shorter, and the the forces between the molecules are much higher, which also means more push of the water molecules against the steel ball; the water molecules get closer to the ball on average, so the force between the average water molecule and the average steel "molecule" (I'm going to go to physics hell for this, aren't I? :P) is higher. Since the intermolecular forces are very strong in a liquid, a tiny change in density corresponds to a very large change in the forces involved, and thus pressure. Don't forget that ultimately, the pressure comes from the electromagnetic interactions between the individual molecules, whose strength is inversely proportional to the square of distance. The water at the bottom of the Mariana trench is cold because it is denser than the warm water at the surface - otherwise, it would rise in a convective column and be replaced with less dense water. Liquids aren't ideal gases.
You might also want to consider a closed container entirely filled with a liquid with no surface. There, you can easily see that the pressure is equalised - that's the whole mechanism that makes hydraulics work. Of course, different liquids have different compressibility. This only works when the pressure is high enough to make the differences in the other forces (like gravity) insignificant - the deeper the container, the more pressure you need. To have the oceans behave this way, you would need to apply as much pressure from the top as is on the bottom, which would be quite the endeavour :P Even if you just built a hydraulic column that's a kilometer tall, you'd need to apply a pressure of about 27 MPa (for ocean water) before it started behaving "nicely" - that's 2700 tonnes per square meter, about three times as much as the ground-level atmospheric pressure on Venus.
A: The problem is that you're modeling the liquid like an ideal gas, whose molecules independently bounce off the ball, but liquids are characterized by strong interactions at short distances.
A better (but still inaccurate) model would be to treat the liquid like a solid locally, i.e. imagine each of the liquid molecules connected in a chain by springs. An increase in pressure means that the springs are compressed more and more, so they push outward onto your object more and more. 
In terms of your variables, we should have $F \sim k \Delta x$, not $F \sim 2mv/\Delta t$. In this model, pressure can be transmitted from molecules far away, just like tension is transmitted through a rope. 
