How can I interpolate between two different animations?
The brutal answer is to animate a transition between the two different strips.

First consider how much of the end of the first strip and the beginning of the second strip you want to preserve.  If you want to shave some frames off of one or the other you can do that by adjusting the parameters of the strips (which does not affect the original actions, it just changes how much of that action is incorporated into your animation).

Then create a new strip that bridges the frames between the end of the first strip and the beginning of the second and populate it with keyframes that animate the figure how you want it to move.

One workflow for this process would be 


create keyframe from position (or whatever) to begin a new primary action at the frame where the transitional animation will begin.
Push that new action down into the NLA track using the vv icon.
Alter the End Frame of the new strip to be the end of the transitional animation.
Create a new NLA track ( Add>Add Tracks )
Use Edit>Track Ordering>Down to move that track below the existing track.
Use Edit>Move Strips Down to move the brand new strip into the new lower NLA track.
Scrub the time line to the frame from the second (old) strip to pick up the position from that strip
With the new strip selected, Tab to begin editing its action.
Insert a new keyframe using the value we got from the second strip
select the first strip and change its Extrapolation from Hold to Nothing
Alternatively, move the NLA track with the new strip to the top of the tracks and make sure its Extrapolation is Nothing


I created an animated gif that is too large to put on stackexchange:

https://drive.google.com/open?id=0B2Wy3tK1vORHc1FCZEFPYWtkZzQ

Now since I was just dealing with the location of a single cube this process was relatively easy.  Since you are dealing with an armature's animation and your animation consists of a large number of fcurves for the orientation of many bones, steps 1 and 9 will have to be repeated for every bone that has a keyframe.  Do not repeat steps 2-8.  Use the single new strip to contain all of the keyframes for all the bones of the transitional animation.