What is the meaning of the negative sign in $W = -\Delta U$? What is the meaning of the negative sign in $W=-\Delta U$?
As far as I understand, $W=-\Delta U=-(U_\mathrm f-U_\mathrm i)=U_\mathrm i-U_\mathrm f$.
While $U_\mathrm i$ is the initial potential energy (before applying the work), and $U_\mathrm f$ is the final potential energy.  
But that doesn't work out when calculating the work done to bring an object from the face of the Earth to a height $h$ above the sea level:
$$W=-\frac{GM_\mathrm Em}{R_\mathrm E}-\left(-\frac{GM_\mathrm Em}{R_\mathrm E+h}\right)=GM_\mathrm Em\cdot\left(\frac1{R_\mathrm E+h}-\frac1{R_\mathrm E}\right)\lt0$$
The result is negative, but a work that is done against a force field should be positive.  
That negative sign always confuses me.
 A: It would help me, but even more importantly you, if you defined what your symbols are supposed to mean. You did that with $U_i$ and $U_j$. So let's be precise together, as an exercise:
Let's explicitly state that we consider a point mass $m$ in a gravity field caused by a much larger mass $M_E$ at the origin of the coordinate system, so that we can assume that $M_E$ does not move. Let's further specify that $U_i$ is the potential energy of $m$ at the initial position, and that $U_f$ is the potential energy of $m$ at the final position.
Potential energies are not absolutely measurable; one can only measure differences in potential energies. So, the potential energy is only fixed up to an additive constant. Now, one may (and should) ask how this constant is chosen in your problem. From the form of the potential energy you used,
$$
U\left(\vec{r}\right) = -G \frac{M_E m}{r}
$$
I conclude that your choice is such that the potential energy is $0$ at infinite distances to the origin:
$U\left(\infty\right) = 0$
For the sake of argument, let's further say that in the inital position $R_E$ is closer to the origin than the final position $R_E+h$, so that your $h$ is greater than $0$. Then,
$$
U_i =
U\left(R_E\right)
=
- G \frac{M_E m}{R_E}
<
- G \frac{M_E m}{R_E + h}
= 
U\left(R_E+h\right)
= U_f
$$
That is, the mass $m$ has lower potential energy closer to the origin.
This means that moving $m$ from the initial position to the final position requires the input of work by some external source. Now, there are two different conventions as to how to label this work; some say that the work that acts on $m$ to move it is called $W$. Others do the opposite, and use $W$ to denote the work performed by $m$ as it moves. These two conventions differ exactly by a factor of $-1$.
So, when you write $W = U_i - U_f$, you choose to say that $W$ is the work done by $m$ as it moves. You can convince yourself of this fact by considering the example discussed above, where $U_i < U_f$. Then clearly, $W<0$, which makes sense, since $m$ does not actually perform work, but work is performed on it in order to move it.
However, when you say

work that is done against a force field should be positive,

you could have said more precisely

if $m$ moves agains a force field, something has to do positive work $W^\prime$ on $m$.

But in the case of $W^\prime$, the choice of convention for the sign of work is opposite to the choice for $W$ you used earlier, so that $W=-W^\prime$, and the apparent contradiction is now resolved. If it isn't, just let me know, I'll try to reformulate.
A: $U$ in your equation in potential energy, and $W$ is internal work.  That is, the work done by forces within the system.  The system in question here comprises the object and the earth, and the internal force is gravity.  The work that you do to lift an object is external to the system, and does not appear in your formula.  
In your scenario, lifting an object "up", the direction of the force is down, and the direction of the displacement is up.  Thus the work is negative, and the change in potential energy is positive, as expected.
The external force of your hand presents a common source of confusion.  It does play an important role, of course:   It provides external work, bringing energy from outside the object-earth system to within the system.
