My Sprint Instinct S30 has a great GPS system. At least for a phone. I've been pretty happy with it, and haven't had any problems unless it can't find the satellites.
I think one of the BF specials is a free s30 with a 2 year plan. Of course, most people would rather eat off their left foot than go to Sprint, but they are very cheap. I've looked at going to VZ, and it would cost me around $40 more a month. That's a lot of jack.