I only know that my device is "hunting" for it target, yet there is very littel noise on the wiper arm of the pot according to the scope, typically not enough to cause the major deviation I'm seeing on the device.

Well, there are other ways for noise to get into the sampled signal on the analog side apart from the ADC input pin. One major factor is the stability of the ADC supply voltages. If they are not stable, then a perfect input signal will not help.

Hunt down the possible sources for noise on the analog side first.

Once that is done, you can try suppressing the noise by applying appropriate filters on the digital side, depending on where in the frequency spectrum your signal is located. Here, you may want to start with "plain" linear filters (finite or infinite impulse response, or a combination) first before trying more exotic (and nonlinear) things like median filtering.

Median filters, if they are used, are usually kept small due to the amount of CPU power required for sorting large arrays. For a 3, 5 or 7-element median filter, a simple bubble sort is sufficient.