My suggestion: abandon any hope of accurate instantaneous pace. Think about it. Pace is distance divided by time, so you always have to measure pace over some amount of time, not instantaneously. You could make that amount of time very short, like a second or less, but if you do, your "instantaneous pace" will be very volatile and jump around a lot because GPS watches measure time with insane accuracy (I don't know, millionths of a second, look at a GPX file), but their measure of location (and therefore distance) is an estimate and subject to a lot of error.
So it's much more useful to look for reasonably accurate GPS (which most decent watches have now) and use some kind of lap pace rather than instantaneous pace. Then you just keep an eye on your lap pace and see if it's going up or down. The Garmin 2XX line has 1-second accuracy in lap pace, while the 45/55/etc. line only has 5-second accuracy, my one complaint about the 45/55 line.