What is force? How does a constant force output a nonconstant power? For a constant force, $P=Fv$. I understand the mathematical derivation of this, but this seems to me, intuitively, to be nonsense. I feel that my discomfort with this comes from a fundamental misunderstanding of force and Newton's Second Law, so I'm not really looking for any mathematical explanation. So, to begin:
How is it that a constant force does not add energy to a system at a fixed rate? Consider a rocket burning a fuel at a constant rate. The chemical potential energy should be converted to kinetic energy at a constant rate, that is, $(1/2)mv^2$ should be increase linearly. The magnitude of the velocity of the rocket would then increase at a less than linear rate, implying a nonconstant acceleration and therefore, a nonconstant force/thrust (F=ma).
If force is indeed a "push or a pull," shouldn't that constant rate of burning of fuel yield a constant "push or pull" as well? Clearly not, so I would have to think that, somehow, a given force applied to a certain object at rest would in some way be different than that a force of the same magnitude being applied to that same object in motion. In this sense, is force merely a mathematical construct? What does it tangibly mean, in physical terms? Would a given force acting upon me "feel" differently to me (in terms of tug) as I am moving at differing velocities?
Force being defined as a "push or pull," which is how it has been taught in my high school class, seems rather "handwavy," and maybe that's the issue. It's been troubling me for a couple of weeks and my teacher hasn't really been able to help, so thanks!
 A: There's nothing wrong with any of these other answers, but for another perspective, if you have a constant force acting on an object starting with zero velocity, then it will accelerate with constant acceleration $\frac{F}{m}$, and thus, after $t$ time, will have velocity $v=\frac{F}{m}t$.  This means that the kinetic energy that it has acquired will be given by $\frac{1}{2}mv^{2} = \frac{F^{2}t^{2}}{2m}$.  
Since the power is the rate of energy consumption, we have:
$$P = {\dot E} = \frac{F^{2}t}{m}$$
so, it should be obvious that the power increases with time.  It should also be clear that our expression for $P$ is equal to $Fv$.  
A: Consider objects in a constant gravitational field.  That is, for any object of mass $m$, there is a constant force field $|F| = mg$ directed downwards, toward the earth.  There is then an associated potential energy $U = mgy$ for a distance $y$ from the surface of the earth.  Any object that moves vertically by 1 meter gains a fixed amount of energy regardless of where they started from.  This is what characterizes a constant force field.
So (one thing) force tells us how potential energy changes with position.  If one makes a straight vertical path from $y=0$ to $y=h$ for some height $h$, it should not yield a different potential energy than taking a very circuitous, meandering route.  Each position has exactly one value for the potential energy, and that's all.
Now, consider two objects that travel from the height $y = h$ to $y=0$.  The potential energy difference is $\Delta U = mgh$.  Let object $A$ start from rest at $y=h$.  Let $B$ have some downward velocity.  Clearly, $A$ will lose energy less quickly than $B$, for it takes $A$ longer to reach the ground.
That's why velocity affects power gained or lost.  Energy losses in a force field depend only on how that force changes with position.  If positions are traversed more quickly, then any changes must occur more quickly.
This line of reasoning depends on the notion of fields, rather than forces from things other than fields acting on objects.  Nevertheless, it is rare in physics that force explicitly depends on time (rather than depending on position, which in turn may or may not depend on time).
Finally, I urge you to think more closely about momentum, as it is a key concept in physics and more than just a handy quantity to use.  Momentum is intricately tied to the concept of mass.  If only velocities mattered, we would have no concept of inertial mass at all, for you could add objects velocities together blindly without regard to how much stuff there was.  Mass serves to tell us that, more or less, heavier things matter more than lighter things.  A heavy object moving slowly can matter just as much to a problem as a light object moving quickly.  How momentum changes directly leads us to the notion of force.
A: This is a couple years old, and the querent has probably long since graduated the classes they were taking. But I used to have some trouble with this, and all the "this equation tells us it's true" approaches didn't really help conceptualize it, so maybe my approach will help someone else with a similar question in the future.
The way I always thought about it was a merry-go-round. At first, it's stationary. You push with some force, the merry-go-round starts spinning. So now it's moving a bit, you grab the next bar on the edge and push some more, and it starts spinning faster. Eventually, it's spinning quite fast.
So now, in order to spin the merry-go-round more, your hand has to rapidly accelerate to catch up to the moving bar, then when you make contact you can start accelerating the merry-go-round some more. But most of your force was used up trying to accelerate your hand, so you can't get much force on the merry-go-round.
Eventually, the merry-go-round is moving so fast that your hand accelerates until it's just barely touching the bar, but can't actually push on it.
The moral: the faster something is moving, the less force you can put on it because a lot of the force is wasted on your hand to catch up with the moving object.
In our case, we're saying force on the object is constant no matter it's speed. As it goes faster, that means there's constant force on the object, plus ever-increasing force just to catch up to the object to start applying that force. More force requires more power.
The same thing happens with a motor that spins gears to accelerate an object via tires or chains, etc. As you go faster, you need to change gear ratios to keep the engine at a speed it can handle. Lower ratios mean the engine speed goes down, so you can go faster, but it also reduces the torque multiplication, so you can't accelerate as fast at that higher speed.
In order to maintain constant acceleration, you need to produce more torque at higher speeds to make up for the gear reduction. More torque requires more power.
These examples involve a stationary object accelerating a moving object. What about a rocket or something? Well, to accelerate this way, we need to launch mass out the back of the rocket at high speed. If we keep launching it at the same rate (mass per second) and speed (meters per second), we get constant acceleration. But there's a problem. We also have to accelerate the reaction mass we're using to accelerate.
So to launch a bunch of mass out the back at some speed, it takes some amount of energy. But to launch the same mass out the back at the same speed once we've already started going, we have to first accelerate that mass to our present speed (if we didn't accelerate it, it wouldn't be in our rocket, so we couldn't use it to go faster). So we spend some amount of energy getting it to our present speed before spending more energy launching it out the back.
The faster we go, the more energy it takes to get the next bit of reaction mass to the current speed, just so we can throw it out the back to go even faster.
In all cases, constant acceleration requires constant force, which requires more and more energy per second as we increase our speed. More energy spent per second requires more power.
A: 
How is it that a constant force does not add energy to a system at a
  fixed rate?

Because the velocity isn't constant.  Think of it this way; the force is constant but the distance through which the force acts, per unit time, and thus the amount of work done by the force, is changing.
For the energy to change at a fixed rate (for the power to be constant), the work done per unit time must be constant; the force would need to decrease in inverse proportion to the speed.   
As an aside, in the case of a rocket, you must also consider the energy of the exhaust products, i.e., the PE of the propellants is converted to KE of both the rocket and the expelled combustion products.
Also, since the rocket is expelling mass, the acceleration of the rocket, for a constant thrust, will not be constant
A: I know what you mean. "Force" is quite a strange concept. Some thoughts:
F * x = E = W  (if you think in one dimension)
Force applied along a way is energy. 
If you want something that you can apply over time and get energy, you are looking for power.

I would have to think that, somehow, a given force
  applied to a certain object at rest would in some way be different
  than that a force of the same magnitude being applied to that same
  object in motion.

That is kinda correct. The faster the object is moving, the more power is applied: F * v = P
Getting back to your rocket example, where the engine burns fuel at a constant rate. So, the POWER of the rocket machine is constant, power * time = energy.
Also, force * speed = power. That means as the speed increases, the force that the engine applies to the rocket slows.
As you said, the rocket should gain kinetic energy linearly with the time: E_kin = enginePower * time. Since E_kin = factor*v^2, we get v^2 is proportional to the time, which in turn gives v = somefactor * sqrt(time). The speed is propotional to the square root of the time. Since force times speed should be constant, the force is proportional to the inverse of the square root of time. 
In other words:
Accelerating at high speeds costs more energy than at low speeds. If you push on something that is fast (you apply force), you will waste more Energy doing so because you do more way, do give a Rocket constant acceleration, you must burn more and more fuel.
"Pushing" or "pulling" for a human being is always connected to energy consumption, even when you push a resting object. (It is something with our muscles, I think.) Force isn't connected to energy consumption. When you think about pushing, you probably think rather about applying power than about applying force.
PS:
I know these kind of questions, when you think about something, and the more you think about it, the less it makes sense. And then you try to ask somebody who should know, but they don't understand your problem, and then you wonder if they are all stupid. 
There is also the other kind of questions where you know you are right and they are wrong, but nobody wants to hear it.
It can be frustrating.
PPS:
There is some barrier between the physics and the things we experience. You take a situation translate it to a formula, do some math and translate it back. This translation process is blurry. You can write a lot about the interpretation of a theory (here, we have been interpreting classical mechanics), but you will use words for that, and words are not precise. 
It is a very good thing that you try to get a non-abstract understanding of the basic physical laws. You might be on the way to become a good Physicist. 
A: A constant force applied to an object at has the same 'effect' (in terms of acceleration) as it has on object moving at constant velocity, but different 'effect' in terms of kinetic energy. This is because the velocity of an object is relative to some (inertial) frame of reference. An object is deemed 'at rest' or 'moving with constant velocity' when measured with respect to some reference. An object 'at rest' has a constant velocity, namely, zero. This is just a statement of Newton's 1st law.
Kinetic energy is quite different from force. Kinetic energy depends on your frame of reference.
Suppose you're traveling in a spaceship with constant velocity though space. The kinetic energy of the spaceship is constant. Now you turn on the rocket boosters, hot gases are emitted at high velocity from the back of the rocket. Power is transmitted to the spaceship and you accelerate away further into space. As long as the rocket is switched on, you will experience acceleration. It will appear as if the power of the spaceship is constantly increasing!
But wait, if the rocket is applying a constant force, I can understand the kinetic energy of the spaceship increasing, but how is it that its power is increasing and not constant? Isn't the rocket a constant power machine!?
The reason for the apparent discrepancy is that if all of the rocket’s energy is transferred to kinetic energy of the spaceship, then the spaceship will accelerate. Also, as long as the force of the rocket is in in the same direction as the spaceship's instantaneous velocity, your speed will increase and so will your power! 
To help your intuition get a grasp of this, think what would happen if you suddenly noticed your spaceship was heading for a large asteroid. If you don't switch off your rocket, the power of the impact will be huge!  In fact, as long as your rockets keep thrusting your spaceship in the direction of the asteroid, the power of the impact is increasing. Even if you turn off your rocket, you will still be traveling at constant velocity toward the asteroid and will be doomed. The power of the impact is 'fixed' by your speed. In fact, to reduce the impact, you have to reduce your velocity (ie: accelerate in the opposite direction). Say you put two retro-rockets on full reverse-thrust, you will experience a force away from the asteroid, even though you are still traveling towards it, until at some point, you will appear stationary with respect to the asteroid before accelerating away from it.
Now, if you want to land on the asteroid, you must adjust the power of your retro rockets to reduce your speed such that at the speed is close to zero at the instant of the impact, otherwise your shock absorbers must be good enough to absorb the extra energy!
Constant force does not add energy at a fixed rate!
You will have noticed this when you try and push-start a car. When the car is stationary, your your force has little effect on the car. Once the car starts moving though, the force you apply is easily translated into kinetic energy!  Of course, this is due to the momentum of the car.  Its also easier to push an empty car from standstill than a full one. By the same token, more 'brake power' is needed to stop a heavy moving car (in a given time), the faster it is traveling.
A: Power and acceleration are not related.  Power is the rate of doing work, (force X distance / time).  It's a "squishy" thing.  For example, it may take the same force to slide a box across the floor the same distance, but the faster you slide that distance the higher the power.  Same total energy, different value for power.
A constant force creates a constant acceleration on a given mass.  The kinetic energy of the mass increases directly proportional to the rate of acceleration and time (and so velocity).
Power doesn't work that way, it is velocity dependent [force X (distance / time)].  For example, it is easy to demonstrate that a mass could be decelerating while the power is still increasing.
Also, "more power = more acceleration" is true only for discreet values of velocity.  Constant mass and power, acceleration decreases with velocity.
Since force = power / velocity, with constant power, the greater the velocity the less the force and so the less the acceleration.  
