How could I create a high-precision voltage with the atmega128?
First the accuracy. Your total range is 17V, so 0.5mV in 17V is 1/34000, just a little bit over 15 bits. As 0x6d64 notes that's a lot to get from even a multiturn potmeter. Let's see. Most multiturn potmeters are wirewound, the one I have here in front of me has a diameter of about 15mm for the wire path. If the wire is wound at a 0.5mm spacing then you can have \$10 \times \dfrac{2 \pi \times 7.5mm}{0.5mm}\$ &lt; 1000 steps or less than 10 bits.
But let's look for a 16 bit resolution anyway, then you're safe. The same type of solution applies for a lower resolution as well.  

Then there's the current. As I understand it you want to draw several mA from the potmeter's wiper, CMIIW.

A good solution may be to use a Multiplying DAC, or MDAC, followed by an opamp to give us the required output current. The LTC1595 will work:



\$V_{IN}\$ is your 4V-21V input voltage, and via the serail digital interface you can set the output voltage as a ratio of \$V_{IN}\$ like a potmeter would.  

The LTC1597 is a similar device with parallel inputs instead of serial.