I don't know about android, but AAA makes an iphone app that gives verbal directions.
I would never try to use such a thing on a long tour, myself, because it would just tie you to a battery-hogging device, but it does seem a lot of people like the gps stuff.
Don't forget if it's phone-based, it won't work if there's no service.