When approaching a stall, is the first priority to apply power or lower nose?
The instinct drilled into a pilot's head from the beginning as the primary response is "lower the nose" to lower AOA.  If you learn in a glider, that's the only option, so it's easy to drill the instinct into peoples' heads (one reason that glider training before power is so good for pilot skills later).  In a power plane, it's lower the nose and add as much power as you need, but lower the nose must be the first instinctive action.  How much to lower the nose depends...

In a non FBW jet (FBW is another story, the computers taking care of things on your behalf whether you want them to or not), the stall training you get for low altitude stalls (you don't get to an actual stall - you start from stick shaker onset) is lower the nose but not too much, add thrust to maximum, and regulate the pitch attitude to stay just above stick shaker onset (just above the speed tape's "barber pole", the red broken band that indicates the stall region) and if flaps are at landing setting, call for retraction to go-around flap once you have stopped descending and are accelerating with decent speed margin above shaker. 

The objective is to minimize the altitude loss as you recover airspeed.  At shaker onset you still have some margin above the actual stall and if you're close to the ground you don't want to dive, so you just tease the pitch to hold it on the edge of shaker.  You will generally use this procedure for any stick shaker event in denser air, below, say, 10000 or 15000 ft.  As a general rule, you do not make configuration changes with gear and flaps until you have got yourself in a good situation energy wise (not sinking, accelerating - although there may be variations from a/c type to type) because retracting flaps can increase your sink rate and the standard procedure with gear is not to retract until there is a positive climb rate.

At high altitudes, especially above 30000 ft, the stick shaker recovery method is much more aggressive and you are trained to actually push over enough to lose several thousand feet and not be concerned with altitude loss. In the thin air the practice of teasing the pitch to stay just above shaker doesn't work so well, because the air is thin but the inertial mass of the machine is unchanged and that can get you into trouble if you fly it the way you do down low.  You can find yourself back into the shaker/pusher/stall break region if you work the pitch to manage AOA on the edge of shaker the way you would close to the ground.

One of the events that lead to special high altitude stall recovery training during recurrent training was this famous (within the business) Pinnacle Airlines incident with a CRJ200 (quite a harrowing read; I don't think it was mentioned in the report, but the post crash fire was caused when they slid into a back yard garage with a meth lab in it).