Suggestions for simple *nonlinear* animation package?

#1 Try Blender, it is worth.

#2 XSI, Maya and Max can all do NLA (not sure if Lightwave can but I am betting it does since NLA is pretty standard now). But since you started with Milkshape I am guessing that is probably out of your budget range.

#3 LW's been able to do it since 7 (or before). Truespace is an inexpensive NLA solution as well. Not sure on a comparison of quality between systems, though.