Here in China, there's AutoNavi and Amap, both free and offer voiced navigation. But these only cover China and voiced instructions are in Mandarin.
There's one called MapFactor Navigator which uses Open Street Map. Not tried it though. Anything else like TomTom or Route 66, you're going to have to pay I think.