There are multiple ways to view this.
The easiest, I think, is that kinetic energy scales with the square of velocity
$$K=\frac 12 m v^2$$
If we assume that the rocket booster supplies a constant acceleration, then comparing initial and final velocities we find that
$$\Delta v=v_\text{final}-v_\text{init}=at$$
So for the same amount of time, the change in the velocity is the same, regardless of what the starting velocity actually is. Since we have a squared dependence on the velocity in $K$, this means that the kinetic energy increases more if we started out with a larger velocitiy. i.e.
$$\Delta K=\frac 12 m v_\text{final}^2-\frac 12 m v_\text{init}^2=\frac 12 m (v_\text{final}-v_\text{init})(v_\text{final}+v_\text{init})=\frac 12 m\, \Delta v (\Delta v+2v_\text{init})$$
So as we can see, the sum of the velocities in the expression for $\Delta K$ is what contributes to a larger change in kinetic energy. Since the work done is equal to the change in kinetic energy, it must be that the rocket does more work when we start off at a larger velocity.
The second way to view this, which you could argue is the same as the first, is to look at the definition of work
$$W=\int\vec F \cdot \mathrm d\vec x$$
Or in one dimension with a constant force
$$W=F\,\Delta x$$
Now, once again assuming a constant acceleration, we know that
$$\Delta x = \frac 12 a t^2 + v_\text{init}t$$
So that the work done is
$$W=F\left(\frac 12 a t^2 + v_\text{init}t\right)$$
Once again, we see that the initial velocity determines the work. A qualitative explanation from this is that when the velocity is larger, then the object covers more distance in the same amount of time. So if we look at the time the force is being applied, the faster it is moving the larger distance the force is applied over. Therefore, we get more work done if the object is initially moving faster.
The supposed issue behind all of this is that is seems like we are getting more energy from applying the same force for the same amount of time. But if you work through it you find that this is no issue at all. This is even true for objects falling near the Earth's surface. Even though the force is constant, gravity does more and more work on the object while it falls. Or in other words, the rate of energy conversion from potential to kinetic energy increases as the object falls.