Hmmm, I'm not really sure on the best process, as I've never done anything like this before, but I would probably use the collapse tool, to bring down the polys. This would work best in the areas with simple Geo, like the legs and arms. Anywhere else it could get messy. I guess you could try using it in other ares of the model, and see what happens. I tried it just a few minutes ago in Maya, and it works great on simple objects. Plus It reserves the UV's
I tried it on a complex object, and it works well, but if you do it too much you start to loose allot of form, and also the UV's start to get a bit Screwy. Simple because there isn't enough UV's to hold the original shape.
I can see by playing with some tools that the De-Resing isn't going to be that hard, but rather keeping the UV's intact is going to require a bit more work.
Have you heard of the Transfer attributes tool? This would allow for you to De-Res your model, anyway you like, and then simply transfer the UVs positioning over from the original model to the new.
I've never used this tool for UVs before, but from what I've read it sounds like a cure to your problem, or at least an aid to your effort.
Let me know if you need any hep with the Transfer tool.
"Your weapons are no match for ours! People of Mars, surrender!"
"Um, this isn't Mars. This is Earth."
"Earth? Earth-with-nuclear-weapons Earth?"
[long pause] "Friend!!"