You are coming up with really strange interpolations because you're in Euler mode and encountering gimbal lock. Euler is notorious for gimbal lock problems, especially for animators who are unaware of how Euler rotations work. The best way to avoid this problem is to use quaternion rotation mode. You change the mode in the object transform properties. Quaternion math makes two orientations interpolate in the shortest path, meaning there is no flipping or spinning. You can think of this as "the shortest distance between two points is a line."
If you really, absolutely need to stick with Euler, the trick is to use as little rotation as possible to get the desired orientation. The Z axis will do most of the work in this case. Then tweak the X and Y values to get the final orientation.
Here are three tips to make working with this object much easier:
Work with the manipulator in gimbal mode. You can change this in your 3D view header or by pressing AltSpace. This mode gives a great visual cue to how the Euler rotations are compounding on each other.
Give the object a zeroed orientation aligned to the cardinal (global) axes. This will make it infinitely easier to visualize and predict what effect your rotation axes will have on the object. I generally point my objects to -Y or +X, but the choice is yours.
Lastly, play with rotation order. The default Euler order is XYZ, but the best mode is dependent on your scene. The mode to set it to is entirely arbitrary, but some work better than others for a particular scene. With the alignment in the last tip, my rotation order would remain XYZ. Then the only axes I would need to animate the object as I see in your scene would be Z and Y.
For another explanation, see my answer on this similar question.
