There's always confusion with this topic when it's not well explained. It's all inside "work-energy theorem", which says
$$\Delta E_k = W$$
But we'll make a distinction here: work done by conservative forces and work done by non conservative forces:
$$ \Delta E_k = W_C + W_{NC} $$
And now, we just call "minus potential energy" to the work done by conservative ones
$$W_{C}:= -\Delta E_p$$
We do this for convenience. We can do it, because a conservative force is such taht can be written as a substraction of a certain function $B$ like this:
$$W_C=B(\vec{x_f})-B(\vec{x_0}) $$
We just decide to define $E_p=-B$, so $W_{C}=-\Delta E_p$. We include that minus sign so that we can take it to the LHS:
$$ \Delta E_k = W_C + W_{NC} $$
$$ \Delta E_k = -\Delta E_p + W_{NC} $$
$$ \Delta E_k + \Delta E_p = W_{NC} $$
$$ \Delta E_m = W_{NC} $$
So the increment in mechanical energy is always equal to the work done by non-conservative forces. If there are no non-conservative forces, then $\Delta E_m=0$ and energy is conserved (that's why we call them like that.
(read it slowly and understand it well)
So, having this in mind, I think your confusion arises because of that famous "artificial" negative sign.
There are many formulas, and it's typicall to have a mess. It's all about surnames: $\Delta E_k = W_{Total}$, but $\Delta E_m=W_{NC}$. The subindices are the key.
The force of engines is non-conservative. Hence, their work contributes to total mechanical energy.
Gravity is conservative, so we can work with its potential energy.
If there is no increase of kinetic energy, that means
$0 + \Delta E_p = W_{NC}$
So engines are only increasing potential energy. But that means
$$-W_C = W_{NC}$$
Of course, if there's no gain in KE, no acceleration, there's equilibrium. The work of the engines is compensating the work of gravity.
- Negative work is always positive $\Delta E_p$, by definition.
- More altitude means more $E_p$, you are right. But here energy is not conserved (engines). Normally, increasing height would decrease $E_k$, but we're adding work so taht $E_k$ stays constant.
- $\Delta E_k=0$ implies $W_{Total}=0$. That means gravity is making negative work, and engines are doing positive work (equilibrium). The thing is that potential energy variation is minus gravity's work.
Best Answer
I have highlighted some key word lacking in your revision. Also, work has a very specific definition. The difference in gravitational potential difference between $\vec{r}_1$ and $\vec{r}_2$ is the negative of the work done on a unit mass by the external gravitational field as the unit mass moves from $\vec{r}_1$ to $\vec{r}_2$.
As an example, consider a mass $M$ located at x=0 and producing the gravitational field in a space. A unit mass moving from $x_1 > 0$ to $x_2 > x_1$ will have work done on it by the field: $$W = \int \vec{F}\cdot d\vec{r} =\int_{x_1}^{x_2} \frac{-GM(1)}{x^2} dx= GM\left(\frac{1}{x_2}-\frac{1}{x_1}\right).$$
The difference of gravitational potential is the negative of this. This makes sense because the field is doing negative work on the unit mass as it moves away from $M$. The gravitation potential is getting higher which agrees with moving opposite the force.