Here is the basic idea:
V1 is the filtered PWM output and R2 is your sensor. U1 is voltage to current converter, with current through the load R1 being I = V1/R2. This means that voltage across R1 depends on both inputs. U2 and U3 is an instrumentation amplifier with gain 10, which amplifies the voltage across R1.
With R1 = 100 Ohms and V1 = 0..5V the circuit works for R2 = 50..5000 e.g. across two orders of magnitude, which from what you say should be enough.
What you do is take out and compare it with reference voltage (4V would be appropriate here for maximum dynamic range) and use successive approximation on V1 to get out as close as possible to the reference voltage. From V1 and known voltage drop across R1 (e.g. reference voltage) you can now calculate value of R2, your sensor. This will of course get you result only within the resolution of PWM, but you can use second instrumentation amp to amplify the error (difference between out and reference voltage) to get it within the range of your microcontroller's ADC and this will get you additional bits of resolution.
You need two opamps (U1 and comparator) and two instrumentation amps. Use real ones instead of making them from opamps, because the imprecisions of resistors and opamps will introduce error.
If two orders of magnitude were not enough, you can replace R1 with digital potentiometer to get another degree of freedom. I have never worked with one, so I don't know how precise they are and whether such solution would need some calibration or not.
Also, I should mention that it was jpc who came with the idea.
UPDATE:
Ok, I have to agree with OP that this is not really the the answer to his question (though it solves the problem technically). I allowed myself to be carried away by "adaptive amplifier" in the title as an excuse to do some analog design. Forget everything writen above, unless you want to learn something (little) about opamps. Here is, I hope, better answer and much simpler solution:
Use resistive divider powered from a voltage regulator (to separate it from other circuitry's noise), with upper resistor set to about the maximum resistance your sensors can have (Rmax), and with the lower resistor being the sensor.
Set the reference voltage for your ADC to half the voltage regulator's output.
Then you sample the voltage on the sensor with your ADC. This way you need only one single-ended channel per sensor. I made ADC recommendation in the other post.
If you use 10 bit ADC that is integrated in the microcontrollers you mentioned, you will not get much of a dynamic range, though. Enhancing the range using analog circuitry, like the one I originaly posted, would add too many additional parts, which is why I would recommend simply to use some 24 bit ADC, like the ADS1256 I recommended in the other post, because it will give you low noise and high dynamic range, in a single chip (plus the reference, which is tiny, and the voltage regulator, which can be also tiny - you can also try to leave the regulator out and power the resistive divider directly from the reference - this will rob you of 1 bit of resolution, but there are plenty of them anyway). You will have to do some number crunching ("Auto-calibration by finding min and max values in a given analysis window" - is a good idea), but that's easy in this case.
I hope this is little more usefull.
UPDATE 2:
This is the last one: I have been going through MSP430 microcontrollers from TI and I have found that some of them have 16 bit sigma-delta ADC with internal reference. Namely MSP430F2003 and MSP430F20013. That would be your one chip solution if you are willing to give up on Atmels. Very low power too. And they have in queue microcontrollers with 24 ADCs, but these are not in production yet. Than there are also PSoC microcontrollers from Cypress, which have 20 bit sigma-delta ADCs (PSoC 3 and PSoC 5 series), also with reference. These would be even better.
Best Answer
I think you should get to the bottom of what is causing your errors. Either you are missing steps or your mechanical setup is too flexible or has backlash in the nuts/bearings. Your homing switches may also have poor repeatability if you are not using an edge finder to locate the tool precisely. Or perhaps it's a combination.
Things like backlash and flexibility are very difficult to compensate for with software. For example, depending on the direction of cut you may start off with the tool in the right position but as soon as it bites in kerchunk and you've dug into the work as the cutter pulls itself in. Or you may be doing climb milling and the cutter runs well outside of the desired path if the gantry and slides are too flexible.
Anyway, glass scales are a sort of mid-priced way to measure a few microns down to 1um resolution. Accuracy over the full scale might be 10-15um over 1m for a cheap one. They typically have a quadrature 5V digital output (incremental), some may have quadrature sinusoidal signals. But each axis will probably cost about as much as you've put into this so far, and there is no guarantee you will be able to do much better in part accuracy. Photo from this page
If you win the lottery you can consider Renishaw and Heidenhain encoders, which can reach resolutions orders of magnitude less than a wavelength of light and do it with absolute measurement.