в гис русса, которую я поминал, пользуются векторные карты. вся россия - примерно 200 мег. плюсом карты городов. например, подробный новосибирск с автопрокладкой маршрута - 4мега. Омск без автопрокладки - 2 мега. Вся россия обычно не нужна, так что можно надергать квадратов, в которые умещается примерный маршрут и уложиться мег в 10-20. Тогда даже без карточки памяти все в кпк вместится.
Надо только иметь в виду, что эти карты создаются на добровольных началах. то есть качество и подробность сильно зависит от человека, ведущего конкретный квадрат или город. ну и от количества добровольцев, которые ему инфу сбрасывают. Если размер карты города исчисляется мегами - она наверняка с детализацией до домов. Карта, где только сетка улиц - умещается в один мег (екатеринбург, например - порядка 200кил).
Существуют и коммерческие карты, но их я не юзал и про них ничего не скажу.
Чтобы говорило голосом, куда ехать - карты должны быть векторные (ози эксплорер отпадает) и они должны поддерживать маршрутизацию. То есть не только прога, но и сама карта. Для гиссы, навитела (российские проги), для том-том'а и кучи других буржуинских - такие карты есть. но не для любого места планеты, так что лучше проверять заранее. опять же, качество прокладки маршрута, говорят, бывает сильно разное.
По москве, опять же PocketGPS Pro Moscow - точно умеет разговаривать :) Он, считается, даже пробки учитывает при прокладке. Не разбирался правда, кто инфу о них передает, но видимо есть какое-то отслеживание ситуации.
В машине, автобусе, поезде - работает. В самолете еще не пробовал, но препятствий не вижу. Если поймает больше двух спутников, а в самолете наверняка поймает - будет еще и высоту показывать. Правда не над землей, а над геоидом, но все равно прикольно.