This is obviously a draft. How did you even get here?

You're sitting on a bicycle or in a rocket ship, stationary. This gets boring, so you accelerate to 1 m/s. After cruising for a while you get bored again, so you accelerate some more, up to 2 m/s. What took more energy, getting from 0 m/s to 1 m/s, or getting from 1 m/s to 2 m/s?

Answer 1. Once you're cruising at 1 m/s, we may as well use the inertial reference frame which is moving at 1 m/s with you, in which you are stationary. Then the second spurt of acceleration corresponds to speeding up from 0 to 1 m/s, which is exactly what the first spurt did in the stationary reference frame. So the two take the same amount of energy.

Answer 2. Just measure the kinetic energy differences. Kinetic energy is proportional to the square of speed, so the first spurt of acceleration took $1^2 - 0^2 = 1$ unit of energy and the second one took $2^2 - 1^1 = 3$ units of energy, which is 3 times as much energy.

The problem is that both of these answers seem intuitively compelling. For a similar problem, I thought of one answer but not the other, and it seemed so clear that it wasn't even worth double checking. After I realized what had happened, I started on a quest to update my intuition so that the same failure mode doesn't happen again. I haven't entirely succeeded, but I was at least able to console myself that many people with very good physical intuition also found this confusing. Let's review some possible explanations.

"You can't ignore friction because bicycles can't work without it"

"... and I don't own a rocket ship, so your question doesn't make sense." Nobody I talked to really proposed this answer, but I did run into a small number (~0.6) of lawyerly personalities who, when confronted with cognitive dissonance, immediately look for a loophole to relieve the pressure. We know better than to do that; this section is just here to give the other parts of your brain a few more seconds to find their own resolution for the paradox rather than anchoring to one of the resolutions proposed below. If you find a good one that I haven't listed below, please send it to me or add it to the discussion page.

"It depends on your reference frame"

Maybe the energy expended depends on reference frame. After all, different reference frames disagree about how much total energy an object has. This is a fine first step, but it doesn't stand up to scrutiny at all. We would have noticed long ago if it were possible for the physicist on the bench to observe an operation consuming 3 gallons of gas while another physicist on her leisurely 1 m/s stroll observes the same operation to consume only 1 gallon of gas. Answer 1 and Answer 2 can't both be correct.

"Answer 1 is wrong"

Here's another way to think about Answer 1:

Answer 1′. In order to accelerate 1 m/s, you have to apply some amount of force $F$ for some amount of time (say 10 seconds). This same amount of force for the same amount of time will accelerate you 1 m/s, regardless of your starting velocity. Applying a force is what energy expenditure is all about, so the energy expended should just depend on how hard you have to push, and how long you have to push.

Right? Wrong. Work done is force times distance, not force times time.

If you're already cruising on your bike at 1 m/s, getting up to 2 m/s will require the same amount of force for the same amount of time as getting from 0 to 1 m/s, but the pedals that you're applying the force to will move a much greater distance over that time. Three times the distance, in fact. So Answer 2 is correct.

"Answer 1 is correct"

Wait, wait, wait. Answer 1 didn't say anything about work being force times time. You can't just substitute some other argument with the same conclusion. What's wrong with the reference frame argument? Nothing. It just doesn't apply to the bicycle problem we just thought about. If you're cruising along at 1 m/s, then when we shift to the reference frame in which you're stationary, it doesn't look at all the same as when you were going 0 m/s. The ground is now moving backwards underneath you at 1 m/s!

If you're in the rocket, then the argument in Answer 1 is completely valid. Rocket ships are not the same as bicycles! To power a bicycle, you have to throw the Earth backwards relative to you however fast you want to go. The faster you want to go, the faster you have to throw the Earth. But to power a rocket ship, you just have to throw something backwards relative to you.

So how am I going to update my intuition so that I'm less likely to make the same mistake in the future? By remembering that you can't just "apply a force" to something. You have to push off against something else. I don't think I could have been confused by Answers 1 and 2, or thought of the wrong one, if I'd kept in mind the thing you push against.

Epilogue: what's right about Answer 1′?

There is something disturbing about the fact that the amount of work you do on an object depends on your reference frame, and it's unsatisfying to just say "work is force times distance, not force times time." Force times time feels like something real and important; can that really just be a poor heuristic that my brain refuses to let go of? Force times time is impulse, or change in momentum. Now that we know that we ought to keep track of the thing we're pushing against, we can ask, "how much work is done by a given amount of impulse?"

Let's fix our setup and notation. Suppose I have two masses $m_0$ and $m_1$, travelling with speeds $v_0$ and $v_1$, respectively (for homework, you can work out the (>1)-dimensional case, where the speeds are vectors). Then the momenta are $p_i=m_iv_i$ and the kinetic energies are $\frac{1}{2m_i}p_i^2$, for $i=0,1$. Suppose somebody applies a force to $m_1$ by pushing off of $m_0$, for some amount of time, then they confer some impulse $J$ on $m_1$ and $-J$ on $m_0$. We can compute the total work they've done by looking at how much the energy of the system changed:
$$\begin{align*}
\text{work}
&= \Bigl(\overbrace{\frac{1}{2m_0}(p_0-J)^2 + \frac{1}{2m_1}(p_1+J)^2}^{{KE}_{\text{after}}}\Bigr) - \Bigl(\overbrace{\frac{1}{2m_0}p_0^2 + \frac{1}{2m_1}p_1^2}^{{KE}_{\text{before}}}\Bigr) \\
&= \frac{-2p_0J}{2m_0} + \frac{J^2}{2m_0} + \frac{2p_1J}{2m_1} + \frac{J^2}{2m_1} \\
&= (v_1-v_0)J + \bigl(\textstyle{\frac{1}{2m_0} + \frac{1}{2m_1}}\bigr)J^2 \\
&= (v_1-v_0)J + \frac{1}{2}(\Delta v_0 + \Delta v_1)J
\end{align*}$$
where $\Delta v_i = J/m_i$ is the absolute change in speed of $m_i$.

As expected, the work depends on more than the impulse. It also depends on the difference between their speeds and on how much their speeds change (or equivalently, on their masses). Those things are agreed on by people in different reference frames (let's ignore relativistic speeds for now). So even though the amount of work you do on a given object depends on the reference frame, the total work done by exerting a fixed amount of impulse is independent of reference frame. Whew! It would have been crazy if that weren't true.