How is the work done to push a planet over 1m with 1N the same as pushing a feather over 1m with 1N? Assume there are no other forces acting and the rocket+fuel described do not weigh anything. Also, by rocket I mean engine/thruster, not space shuttle.
Suppose you have a planet, say of mass 1,000,000,000 kg and you push it with a rocket which exerts a force of 1 N. This will accelerate the planet by $10^{-9}\, m/s^2$.
Then, suppose you have a feather of mass 0.005 kg and push it with the same rocket which exerts a force of 1 N, accelerating it by $200\, m/s^2$.
It follows that the feather will traverse a distance of 1 m much faster than the planet and thus spend much less rocket fuel to do so. So, the energy used to propel the planet must be much more than the energy used to propel the feather.
But, work done = force × distance, $1 \times 1 = 1\, J$ for both the planet and the feather. I think I have misunderstood something. How is this possible?
 A: The work done on the planet (or feather) is equal to the change in KE of the planet (or feather). This is the work-energy theorem.
If they start from rest, they will both have the same KE after the 1m of pushing. The planet will have a huge mass and very small speed. The feather small mass and large speed. The KE will be the same.
The way you "produced" the force doing the work does not enter into the work-energy theorem. You can use more or less energy depending of your "machine", the system doing the work. But this does not affect the change in KE of the system your machine does work on. 
A: 
So, the energy used to propel the planet must be much more than the energy used to propel the feather.

Yes. But that is because the rocket is a special thing. See below.

It follows that the feather will traverse a distance of 1m much faster than the planet [...]

Work is not about duration. It does not depend on time or on how fast. Pushing with 1 N and moving the planet 1 m requires the same work by the force regardless of it taking 1 hour or 1 year or 1000 years.
This might not seem very intuitive at first. If it takes a long time, isn't more energy then spent since the force must be upheld longer?
The answer is no. Think of a table holding up an apple with it's normal force. No energy whatsoever is spent by the table to uphold this force. It can do this forever. Force does not require energy - apart from in specific special "machines".
And that's the thing. The root of your confusion, if I'm right. A rocket propulsion engine (most types of engines to be fair) is such a kind of machine. It takes energy to create the force it exerts. It takes fuel. Fuel is burned at a never-zero rate and so the energy consumption of a rocket does depend on time.
The human body with its contracting and expanding muscle fibres is such a kind of machine as well. Eventually you will get tired of pushing, but the wall doesn't.
When thinking of the work formula $W=\int\vec F\cdot d\vec x$, I like to compare a wall with a balloon (essentially what you are doing, but in a slighty simpler setup):

*

*Pushing on a wall doesn't really make any difference even when pushing hard. Nothing moves. No work is done, you are just wasting your time.

*Pushing on a balloon is easy - it moves far. But it was so easy that no one would say that you did any significant effort. We wouldn't say that you did any significant work to move it.

The first example is your situation.
A: Let's take a Closer Look at the Whole System: It consists of the Planet / Feather (the accelerated object), the engine / thruster, and (and this is important) particles acellerated by the thruster in direction reverse to the pushing force acting on the planet. 
Your massless engine, however it works, uses the energy of the massless fuel to accelerate a) The Planet / Feather, and b) some other particles (usualy the burned fuel) in order to satisfy conservation of momentum. 
The whole Energy of the System is given by:
$$
E = E_{planet} + E_{burned fuel} + E_{fuel}
$$
The whole momentum is given by
$$
P = P_{planet} + P_{burned fuel}
$$ 
To make it short: On your one meter acceleration way, the energy that the planet and the feather get are the same. This isn't true however for momentum: The planet will carry more momentum --> There will be more "burned-fuel-particles" carrying more momentum, and thus also carrying more energy. And that's the energy that is missing in your equation. The whole energy of the system will be conserved. 
To look at it more detailed:
Force is the time derivative of momentum. The thruster pushing the planet / feather with one 1 N means, that every second there is generated a backward flying "burned-fuel-particle" carrying 1 kg $\frac{m}{s}$ momentum. Since the planet takes (as you noticed) more time to move 1 m, the there will be more particles accellerated backwards. They carry most of the energy that is provided by the fuel.  
A: You might find this a bit simplistic, but I just wondered if maybe it helps you if I highlight some basics you may already be aware of...
that work is done to change velocity (accelerate), and an object continues at constant velocity unless work is done to it.
Work achieves a speed, not a distance.  If an object has a non zero speed and no external forces interfere then it will continue to travel until it eventually achieves a great distance.
Compared to the motion subject to friction and air resistance that we typically experience on earth motion in vacuum can intuitively seem "a bit of a freebie". It is indeed cheaper.
