I am trying to understand electric circuits (ie voltage, current, power, and resistance). For the most part, everything makes perfect sense, but for some reason I do not feel as if I understand the proper definition of power. Yes, I understand the formula's $V=IR$ and $P=IV$, but I am a strong believer that you do not truly understand something until you can explain it to someone else in layman's terms (which I cannot confidently do at this point in time).

Perhaps I can explain my confusion using the water analogy (which I'm not particularly fond of, but will use anyone for illustrative purposes). I understand that if water is flowing through a hose (or pipe), the amount of water at a specific spot per second is analogous to electrical current, the pressure to voltage, and the width of the pipe to resistance.

Now let's imagine two hoses... one has twice the resistance (meaning it has smaller physical width than the other). But we also make sure that both hoses have the same current (meaning that the smaller hose has twice the voltage (water pressure)).

If we were to hit some toy windmills with the water coming out of each of these hoses (from the same distance of course), it is my understanding that they would start spinning at the same speed, or another way to put this might be that the work done upon them is the same.

Now this is where my confusion starts, because in this situation, the current is the same for both hoses, but the power (watts) is doubled for the hose that requires double the voltage to maintain the same current (due to it having twice the resistance).

When I think of the word "power" and something that has twice as much of it as something else, my mind instantly thinks it is twice as powerful, and thus can exert more force or do more work on external objects. But here it seems like current is what determines the speed at which the windmills would turn, or how bright a light bulb in a closed electrical circuit would be? In fact, it seems like 'power' in this context is a requirement, or the the amount of effort required to keep the current at a constant rate given a certain voltage. This also makes me think that the the hose with twice the power is less efficient (obviously due to the resistance). But thinking of power like this seems counter intuitive, and perhaps I am not understanding something important here. Is power truly the 'effort required' by the circuit to run or is it about 'potential work' that a circuit can exert on external things. Any clarification is greatly appreciated.

Now lets imagine two hoses... one has twice the resistance (meaning it has smaller physical width than the other). But we also make sure that both hoses have the same current (meaning that the smaller hose has twice the voltage (water pressure)). If we were to hit some toy windmills with the water coming out of each of these hoses (from the same distance of course), it is my understanding that they would start spinning at the same speed.

That's where the confusion comes from -- you're not interpreting the equation $P = IV$ correctly. The equation states that the power dissipated in an object is equal to the current through that object, times the voltage drop across that object.

When we apply $P = IV$ to a resistor, which you've corresponded to a hose, $P$ is the power dissipated in that resistor, while $V$ is the difference in voltage between the two ends of the resistor. For a fixed current, the power dissipated in a resistor with higher resistance is greater, because the voltage drop is larger.

This is independent of how much energy is dissipated in the windmill, which is $I V$ where $V$ is the voltage drop across the windmill. In other words, the amount of power you lose in the hose depends on the pressure drop across the hose, while the amount of power you deliver to the windmill depends on the pressure of the water as it comes out of the hose.

To expand on BowlOfRed's answer, your original premise is mistaken. I read your original analysis and, while it is mostly correct, I think you think equal current = equal speed. That's not correct.
Equal current = equal flow (i.e. litres/second).

In the water analogy, resistance corresponds to area of pipe, so a high resistance pipe has a smaller area. For it to have the same current, and hence flow, then the water must have higher speed.

In one pipe the water is lazily looping out, while in the other it is squirting out with a fizz. Directed into a bucket, they'd fill it in the same time (same current/flow), but the squirty water can do more work (higher pressure/voltage).

If we were to hit some toy windmills with the water coming out of each of these hoses (from the same distance of course), it is my understanding that they would start spinning at the same speed, or another way to put this might be that the work done upon them is the same.

But you said that the pressure in one was higher than the other. That means the water is going to shoot out faster. Each bit of water is moving faster and is capable of doing greater work than an equivalent bit from the one that is moving slower. One will make the windmills spin, but the other will make them spin really fast.

And since the flow rate from each hose is the same, that means the higher pressure hose can do more work.

Forget the analogies and just look at the units

You said it yourself:

but I am a strong believer that you do not truly understand something until you can explain it to someone else in layman's terms

There’s nothing that says layman terms have to be tired old analogues. Just take the thing you are studying at face value:

Voltage

Voltage is measured in (surprise) Volts. But a Volt is a Joule per Coulomb, or:
$$ text{Voltage} = frac{ text{[Energy]} }{ text{[Charge]}} $$

Current

Current is measured in Amps and an Amp is a Coulomb per second, or:
$$ text{Current} = frac{ text{[Charge]} }{ text{[Time]}} $$

Power

Power is calculated as $P=IV$ simply because that’s how the units work out:
$$ text{Power} = frac{ text{[Charge]} }{ text{[Time]}}frac{ text{[Energy]} }{ text{[Charge]}} = frac{ text{[Energy]} }{ text{[Time]}} $$

The analogy to flowing water might be more helpful if you looked at a slightly different scenario. Instead of a hose squirting at a toy windmill, consider a hydroelectric dam. There is stored energy in the water above the dam, there is a system of pipes that guide water to a turbine, and there is an exit pipe that lets the used water flow into the river below the dam. If part of the system of pipes is horizontal, there is some loss of pressure in the pipe from one end of the horizontal stretch to the other. But it's small, and it represents lost energy. There is a large pressure drop between the intake of the turbine and the outlet of the turbine, and that represents energy that has been taken out of the water and put into the electricity. And there is some pressure in the outlet pipe, representing residual energy in the water that could not be harnessed into electric energy.

But in the above description, I have subtly shifted the focus from power to energy. And this is where you need to expand your bag of concepts. Power and energy are closely related concepts, but they are not the same. The hydro electric dam is measured in terms of power (kilowatts) but the electric company sells you electricity in terms of energy (kilowatt-hours). Power is basically energy per unit time. Or put the other way around, energy is power integrated over time. If you take some time to understand both power and energy, you may find it easier to grasp both concepts better than you can grasp either one.

Energy can be measured in Joules, Ergs, or electron-volts as well as kilowatt-hours. The same units can be used as measures of work. In fact the concepts of work and energy are very closely related. Work is basically energy transferred from one system to another.