> So it shouldn't matter at what speed the spacecraft is traveling since the thing it's doing work against (propellant) is always traveling at the same speed as the spacecraft?

That is exactly right.

From the spaceship, when I expel some exhaust, I gain some constant amount of energy. So, it makes sense to me that me acceleration is steady.

From the ground, for a spaceship to have steady acceleration, it must be gaining more and more energy per second. The faster I am going, the more energy I need to gain a little bit more speed. This extra energy comes from the fact that the fuel is moving along with the spaceship - from the ground, the fact that it's moving means it has extra kinetic energy to expend on propelling the spaceship. If you do the algebra, you'll find that the extra quadratic terms on the spaceship's energy and the fuel's energy exactly cancel out.

So the actual effect (constant acceleration of the spaceship) looks the same, but the accounting of which object has how much kinetic energy looks completely different.