If you have cell service with Verizon, consider their navigation software. I use it on an LG VX8300, and it's astonishingly useful.

In theory maps and POIs are always up to date because they are downloaded for each trip (yes, it uses air time, but only for route planning, map downloading, and POI lookup).

Small screen not an issue because while driving I rarely need the maps. Instead the turn-by-turn voice is almost always sufficient.

I travel a lot on business, and at 10 bucks a month, it has served me very well.