This might be a bit too complex for a uC, but there are ways to make the little GPS units work better, with a considerably better accuracy. One of them is called "Differential GPS", which (vaguely) works like this:
Take two GPS units. Put one at a known location -- you'll either have to survey the location yourself, which isn't practical, or just ask and try to find an old survey marker, which has lat/long. Put the other GPS on your robot. Since they are "close enough together", they should both have the same error, but since you know where the fixed one is, you can determine exactly what the error is in both lat and long.
Of course, wikipedia has an article:
http://en.wikipedia.org/wiki/Differential_GPS, but I took a GPS/surveying course in university and we did something similar with two GPS units that didn't require getting the national Differential GPS service to help out...Whether it can be done in real-time is also an open question...