See http://www.cartotype.com for a free demonstration program for CartoType, a portable mapping library that runs on Symbian OS, Palm OS and Windows (so far). There are free maps to download, all of the USA so far, with street-level mapping in a very compact format. Navigation capabilities exist but haven't been put into the demo program yet.
There are Symbian versions of the demo program for Series 60 and P900 series phones. See the web site for details of exactly which models are supported.
The executable programs are completely free and fully functional. They are freely redistributable. Their purpose is to show off the capabilities of CartoType, so as CartoType improves, so will they.