Let us say you're in a non-fly-by-wire tactical aircraft (say a F-15 or an A-4) doing maneuvers in the local MOA, and you manage to depart the jet in some non-spin fashion. Is there a standard procedure for recovering the jet to controlled flight, analogous to how there are standard spin recovery procedures, or is the first step on the checklist "eject"?
The answer depends on the aircraft. In most cases it is No, but for some it is Yes.
The MiG-29 has a green button at the right side of the stick which recovers the aircraft to a wings-level, shallow climb attitude if pressed. Note that the MiG-29, unlike its Western counterparts, is aerodynamically stable over the full angle of attack range beyond 90° and the flight control system can recover the aircraft from any attitude, altitude and thrust permitting.
Here is a quote from someone reporting his experience of flying a Malaysian MiG-29 (link)
The stick has a red autopilot button on the left and a green auto recovery switch on the right for the disoriented pilot, and works by pressing the green panic button. The system recovers the jet to wings level and places the airplane in a slight climb if energy is available. This system is known to be reliable but is not often used. This is most likely due to the necessity of having to recognize that you are spatially disoriented prior to pushing the auto recovery button.
MiG-29 cockpit (picture source). The green button is clearly visible.
Ok, I think I have enough to answer this.
Here is an older training video I found on YouTube for ejection decisions. It looks like it has an aircraft from the A-10 "Family" of aircraft in it (I didn't watch the entire video, but looks like an older variant).
That all being said, a departure is not an automatic "eject" in any aircraft. Departure from controlled flight unless the aircraft is damaged or at a low altitude is typically recoverable, save for a few aircraft that cannot recover from certain departures (flat spins in some types for example).
As I said in my comment, there is no "universal procedure" for recovery. The recovery procedure differs depending on your flight attitude. Speaking from a GA perspective (but I assume it can somewhat be applied to military), recovering from a stall involves stick forward and power in, whereas recovering from a spin involves stick forward and power out (and other things).
The most "universal" method I can think of is to just let the airplane fly itself out. Airplanes (as I stated) are inherently stable in flight and provided you have the altitude and control surfaces have the authority, many types of departures will simply stabilize out and recover in time. Think of pilots in high-G maneuvers, even with G-Suits can sometimes black out (or red-out) for short periods. This is experienced quite a bit during some departures.
A good example of a pilot getting over anxious and bugging out is the Cornfield Bomber Incident where the aircraft recovered after the pilot ejected and continued flying into a field (and even ran along the ground for a long period of time afterwards).
So, to answer the question, the "first item" on the checklist is not "eject". I assume it would be a very short military (and flying) career for the pilot who ejected from a recoverable/flyable aircraft. Ejection seats are extremely effective even at low altitudes and pilots typically fly aircraft until they won't fly anymore, even if it only has one wing.