Why do we say that gravity did work on an object to give it velocity, when it already had that energy as a potential? I'm having a crisis of intuition here.
Scenario
A person takes a dive from a cliff. The person has a potential energy of $E_p = mgh$. As the person falls, they build kinetic energy, and lose potential energy.
On the one hand, books say that the person already had that energy as a potential, and seemingly it was just converted to kinetic energy.
On the other hand, books say that the gravitational interaction between Earth and the person did work according to $W = Fd$ in order to give the person this kinetic energy.
Question
I'm having trouble consolidating these two ways of thinking. Was the energy already present in the object, and simply converted, or did gravity apply work? Or did gravity simply arbitrate the energy conversion?
What am I missing here? I'm assuming that it's some semantic meaning that I'm getting jumbled up in.
 A: Potential energy is a system characteristic and is relative to other possible states of the system. A inert rigid body, a point mass, or anything that is temporarily being treated like one to make the math easy (like a person in free fall) has only one state and can't have any potential energy. When one refers to the gravitational potential energy of a particular point mass, it is shorthand for "the part of the gravitational potential energy of the multiple mass system that would be subtracted if the point mass were moved to the position to which we have arbitrarily assigned as our reference point".
Work is energy transfer from one mathematically definable thing with energy to a separate mathematically definable thing with energy.
Formally, forces do not do work. Fields do work. Forces are a measurement of how much work fields do per unit distance.
The gravitational field is the mathematical abstraction of the gravitational energy-carrying characteristic of the system. It is therefore correct to refer to the gravitational field doing work on the system: energy is going from the gravitational field (a mathematical object that expresses the shape and scale of the system energy) to some characteristic of the system whose energy is not represented in the gravitational field.
In the case of a person falling near a planet, because the person is much less massive than the planet, it's easy to approximate that the work done on the planet, in the frame of an observer initially comoving with the planet, is zero, and all the work done on the person in that frame is the total work done on the system.
Likewise, when the direction of the energy exchange is reversed (climbing the ladder instead of jumping off of the diving board), the person (a reservoir of kinetic energy and chemical potential energy) is doing work on the gravitational field: energy is going out of the person to arrange the planet-person system into a shape that has more gravitational potential energy, and the mathematical object that tracks that potential energy is the gravitational field. One might see this referred to as the field doing negative work on the ascending object, rather than the object doing work on the field. The meaning is the same: "A does -5 joules of work to B" means the same thing as "B does 5 joules of work to A", and they both mean that the energy-carrying mathematical object labeled A ends up with 5 more joules and the energy-carrying mathematical object labeled B ends up with 5 less.
A: The change in potential energy is the negative of the work done by the force of gravity. So, using change in potential energy is just a way of accounting for the work done by gravity.
For a conservative force, the work done by the force is independent of the path taken from the initial to the final position. Gravity is a conservative force, so the work done is independent of the path and is easily calculated as the negative of the difference in potential energy between the starting and final elevations, regardless of how complex the actual path is between the two elevations.
See a physics mechanics textbook, such as Mechanics by Symon, for more information regarding a conservative force and potential energy.
A: The work-energy theorem states that the change in kinetic energy experienced by a body during a given interval of time equals the total amount of work done on it during that interval.
So, when an object falls in the Earth's gravitational field, the mere fact that its kinetic energy increases implies that some force is doing work on it.
It's also true that the object's potential energy is being converted into kinetic energy. However, whenever this happens, it always implies that some force is acting on the object in order to effect such transformation. The force law for that force is the reason why the body is said to have potential energy in the first place.
There is no contradiction between what the books are saying.
A: 
Was the energy already present in the object, and simply converted, or
did gravity apply work?

The gravitational potential energy (GPE) was already present, but not in the object (person) alone but in the Earth-person system. That's because GPE, as well as all forms of potential energy, is a system property due to the relative position of two objects (in this case the person and the Earth).
Gravity enabled the conversion of the GPE of the Earth-person system by doing positive work on the falling person. Ignoring air resistance, gravity is the only force acting on the person. Per the work energy theorem, the net work done on an object equals its change in kinetic energy, or
$$W_{net}=mgh=\Delta KE$$
In this case, where the initial KE of the person is zero,
$$W_{net}=mgh=\frac{1}{2}mv^2$$
The source of the energy used by gravity in performing work on the person is the GPE of the person-Earth system.
Hope this helps.
