I think your confusion pertains to what we're measuring and how we measure it.
So Work is not a property of a given system (like kinetic energy, potential energy, temperature, pressure, mass, volume, etc.). Instead, Work is a process, meaning that a single number doesn't actually tell the whole story.
Let there be a ball of mass m being dropped from a height h from the ground with a gravitational acceleration constant g. We know that the potential energy of the ball at the height h is equal to U1 = mgh. If we let the height of the ball at the ground equal zero, then we know the potential energy at the ground to be U2 = mg(0) = 0. Therefore, the change in potential energy of the ball is equal to U2 - U1 = -mgh. The resultant change in potential energy is negative, because potential energy was lost from the ball.
Now let's examine if there was any work being done. The ball exerted no forces on anything; therefore, it's work is equal to zero. The force of gravity, however, exerted a constant force on the ball in one direction. This force was equal to F = mg, and the distance the force moved the ball was d = h. The work then done by gravity is equal to W12 = F * d = mgh. Note that in this case, the work done by gravity is equal to the negative of the change in potential energy of the ball. Does this mean that W12 = -(U2 - U1), or could this just be a coincidence?
Consider the converse example:
A machine carries the same ball up from height zero to height h. The machine must now exert a force mg to do this. And since it is doing so for a distance h, the work here is again equal to mgh. The ball still exerts no practical forces and therefore does not do any work. It's potential energy has increased, though, from zero to mgh once again. What then about gravity? Well, we see that gravity is still exerting a force mg, and the ball is still traveling a distance h. Does this mean that the work being done by gravity is equal to mgh once again? No. Recall that Work is a process and not a property. Therefore, you can not have a change in Work - that doesn't mean anything or make any sense. So, a negative value for a process like Work, does not mean that we have lost Work, because Work isn't a thing we have, it's a something we have done, or have the potential to do. What, then, does a negative sign imply when talking about Work? It simply implies the same thing it would imply when talking about number lines or other coordinate systems of space/time: direction.
In the first example, the force of gravity acted downward, and it accomplished its goal of moving the ball downward. Therefore, since both the force and the motion of the object acted in the same direction, we give the resultant measurement of Work done a positive sign (i.e. +mgh, or just mgh). If the direction of force is opposite to the direction of motion, we give the value a negative sign (-mgh). So for our second example, the work done by gravity equals -mgh. Wait, but does this mean that the law that the negative change in potential energy equals the work done??? Not quite...
That the negative change in potential energy of the ball was equal to the work done by gravity was in fact a coincidence. The reason for this coincidence is that all of the potential energy that the ball has is coming from gravity. So, it makes sense that the work done on the ball by gravity would be equal in magnitude. The reason it's equal to the negative of the potential is because the potential is a measure of how much energy the ball has ready to use, and Work is a measure of how much is used. Since the ball lost energy for gravity to use it, it makes sense that the work done equals mgh and the potential energy gained equals -mgh.
Consider the following:
The same ball is held up at a height h before being dropped, but now this time has a spring fixed to the ground pulling on it. Let the spring have a constant k and an original, unstretched length L. Now, the potential energy of the ball at height h equals mgh + k(h-L), but the work done by gravity after it falls is still equal to mgh, as now the spring is also doing work equal to k(h-L).
This will become more clear if/when you take a Thermodynamics class.