Its relative velocity with respect to a Cartesian frame of reference fixed on the surface of the Earth may be dropping, but that's not particularly meaningful.
Think of the moon being in free fall, without any external forces acting on it. It would be moving at a constant velocity in a straight line, except the space and time it is in is curved due to gravity. Because of that curved spacetime, the moon appears to accelerate relative to the Earth. It's not actually accelerating, though; it is moving in a straight line at a constant velocity, the straight line just happens to be curved completely around the Earth.
The tidal forces are literal forces, and forces cause acceleration. So, the moon isn't quite moving at constant velocity. The change in velocity means the moon isn't quite travelling in a straight line through spacetime. The orbit changes, and in this case gets higher and slower relative to the Earth.
Another way to think about it. If you're in a space ship at a point X1 in an orbit, you can steer the nose of the ship in the direction you're moving relative to the Earth, and fire your rocket engine. You're now going faster. The opposite end of your orbit, point Y1, will now be higher in altitude than it would have otherwise been. Your relative speed at Y1 will indeed be slower than where you would have been had you not fired your engine, but when you circle back to X1 again your speed will still be higher. When you get to Y1 again, you could fire your engine a second time and increase your speed even more. You'll no longer end up back at X1, but a new point X2 at a higher altitude than X1 was. Your relative velocity at X2 will be lower than it was at X1.
In space, "speed" isn't really velocity, but acceleration. Big rocket engines make you go fast! In The Martian, the main character makes a comment to that effect when he talks about NASA convincing him to strap himself into a hodge podge death rocket, by claiming he'll be the "fastest" astronaut in history.
In a future where humans practically travel to a distant star, a "fast enough" space ship would be one that can maintain constant non-trivial acceleration for many decades. You would accelerate to the halfway point, then turn around and decelerate the rest of the way. Assuming you got fast enough relative to the destination, weird relativistic effects would become obviously apparent and the travellers would perceive space and time compressing.
Just a comment on your second and third paragraphs: it's a bit odd that you invoke general relativity ("curved spacetime") for the Moon's basic orbit, and then discuss classical mechanics ("tidal forces are literal forces") for the second-order effects. Tidal forces are of course also gravitational effects, just differential (i.e., the result of the fact that we are not talking about point masses, but rather extended objects).
Think of the moon being in free fall, without any external forces acting on it. It would be moving at a constant velocity in a straight line, except the space and time it is in is curved due to gravity. Because of that curved spacetime, the moon appears to accelerate relative to the Earth. It's not actually accelerating, though; it is moving in a straight line at a constant velocity, the straight line just happens to be curved completely around the Earth.
The tidal forces are literal forces, and forces cause acceleration. So, the moon isn't quite moving at constant velocity. The change in velocity means the moon isn't quite travelling in a straight line through spacetime. The orbit changes, and in this case gets higher and slower relative to the Earth.
Another way to think about it. If you're in a space ship at a point X1 in an orbit, you can steer the nose of the ship in the direction you're moving relative to the Earth, and fire your rocket engine. You're now going faster. The opposite end of your orbit, point Y1, will now be higher in altitude than it would have otherwise been. Your relative speed at Y1 will indeed be slower than where you would have been had you not fired your engine, but when you circle back to X1 again your speed will still be higher. When you get to Y1 again, you could fire your engine a second time and increase your speed even more. You'll no longer end up back at X1, but a new point X2 at a higher altitude than X1 was. Your relative velocity at X2 will be lower than it was at X1.
In space, "speed" isn't really velocity, but acceleration. Big rocket engines make you go fast! In The Martian, the main character makes a comment to that effect when he talks about NASA convincing him to strap himself into a hodge podge death rocket, by claiming he'll be the "fastest" astronaut in history.
In a future where humans practically travel to a distant star, a "fast enough" space ship would be one that can maintain constant non-trivial acceleration for many decades. You would accelerate to the halfway point, then turn around and decelerate the rest of the way. Assuming you got fast enough relative to the destination, weird relativistic effects would become obviously apparent and the travellers would perceive space and time compressing.