I don't have too much experience in animated models, but mdl naming *_0/_1/_2/_3.mdl works well for lod in free edition too, and 3dsmax "optimize" as I remember keeps animation. (there's a checkbox for keeping material borders if you have more). but there are two other options for it in max, what I always forget... but have some notes somewhere...
in Milkshape reducing vertices results in loss of animation and uv mapping thus I never tested.
but if you prefer free tools, try MeshLab but as I know it does not handle animations: http://meshlab.sourceforge.net/