I'm attempting to answer my own question, so please point out anything that I might've done wrong since I am not an aircraft engineer.
The first thing I do is simplify it to this: The same airplane taken to 2 different environments. In which environment does it fly better? Note this is not necessarily equivalent with the general question, because an airplane designed/optimized for my environment will be a different craft, if for no other reason than the wings and structural loads can be reduced since it only needs to hold up 1/3 weight. More on that later.
Let's call the first environment Earth, and the second environment Thindor. So Thindor has 1/3 the surface gravity of Earth, 1/2 the air pressure, but the same air composition and air temperature.
$$L = 1/2 \cdot \rho \cdot v^2 \cdot A \cdot C_L $$
Now using $V \cdot P = n \cdot R \cdot T$ and $\rho = \frac{P \cdot M}{R \cdot T}$, we see that density and pressure are exactly linearly related given the same temperature (and same volume, same n, and same universal gas constant lol).
In a 1/3 gravity environment, the craft only needs 1/3 of the lift, and the density is only 1/2. So:
$$1/3 \cdot L = 1/2 \cdot 1/2 \cdot \rho \cdot v^2 \cdot A \cdot C_L$$
This is where my lift analysis differs from the previous two answers
A and $C_L$ are the same, but the same airplane is not necessarily moving at the same airspeed to get 1/3 of the lift. Since we've changed lift and density, kept the same A and $C_L$...but the equation is not balanced yet (because we've taken 1/3 of the left side but only 1/2 of the right side), the only other thing we have left to play with is v.
(there's room for confusion here because I said "all else being equal". I guess that's not a well-defined phrase after all. If you think about it, all else can't be equal. We've already established that air density, for example, is not equal in both environments, even tho the only 2 original parameters i changed was gravity and pressure.)
In order to balance it, we need to make 1/2 become 1/3. So $1/2 \cdot x = 1/3$. x = 2/3. But we have to put this inside v squared. Meaning we need $ \left( \sqrt{2/3} \cdot v \right)^2$. So the factor is now approximately 0.816.
$$1/3 \cdot L = 1/2 * 1/2 \cdot \rho \cdot \left( \sqrt{2/3}*v \right)^2 \cdot A \cdot C_L$$
So we only need 81.6 percent of the airspeed to achieve the necessary lift. This means our engines can be a little less powerful.
But there's more, because drag has changed (less drag means even less engine power needed). Here's the drag equation I'm using:
$$D = 1/2 \cdot \rho \cdot v^2 \cdot A \cdot C_D $$
(Wow that looks almost exactly like the equation for lift!? The only difference seems to be the coefficient of lift has been replaced with a coefficient of drag).
Anyway in both environments, A and C_d should be the same, but Thindor density is 1/2 and Thindor v is only 81.6% of Earth v.
$$D_{Thindor} = 1/2 \cdot 1/2 \cdot \rho \cdot \left( \sqrt{2/3} \cdot v \right)^2 \cdot A \cdot C_D$$
So 1/2 and $\sqrt{2/3}$, multiplied together, show that the drag on Thindor is now only 40.8% of the drag on Earth!
I believe this means the required thrust is only 40.8% of the airplane's thrust on Earth.
Now Begin Engine Analysis
I'm not even sure where to begin, and we'd probably have to do a turboprop example (propeller) and a turbofan example (jet engine). ...Not sure how to begin either one...but I know both of them breathe oxygen.
I suppose we can make the assumption that half of the available oxygen will produce half engine power and therefore half thrust. But 50% is greater than 40.8%. Therefore, the same craft can fly at Thindor, with 50/40.8 = 1.225 better efficiency?
ON TOP OF ALL THIS, remember that a craft built on Thindor will have less deadweight, because it doesn't need to be as structurally strong. The wings, for example, can be less strong since they're only holding up 1/3 as much as the weight. Same thing for landing gear and fuselage, and empennage too since torques are less from control surfaces in half air pressure. So now that we're not dealing with the same airplane anymore, we can make ours lighter, meaning Thindor lift can be even less than 1/3 Earth lift, meaning airspeed can be even less, and drag less, and engine power requirements are even less...
So I have to lean towards a positive answer. Yes, it is easier to fly at Thindor.
Can anyone point out anything wrong with my analysis? Because it doesn't agree with the original two answers, both of which got a 1.5 lift-to-gravity ratio and didn't change airspeed (v). Mine, however, got a 1.225 improvement in efficiency.
Also, can someone please edit my equations, because I don't know how to make them look fancy in the right font with subscripts and superscripts. EDIT: thanks Jim2B