OpenStreetMap on Nokia S40
After lots of testing, I found the following applications to be useful on my Nokia 6233. Minimum requirement was the possibility to download map data using the PC and storing it on the phone for offline use. The OpenStreetMap wiki contains much more detailed information. Since the amount is rather overwhelming, here is what you really need to know.
Lots of map data on your SD-card can make the phone annoyingly slow while browsing directories. To solve this, put all the data below one directory in the root folder(!) of the card. Then set the "hidden" attribute of this directory (either using the PC or the very neat MiniCommander). You should configure all the programs you want to use before, because afterwards you will not be able to select this directory in the file browser anymore!
Mobile GMaps
MGMaps displays bitmap tiles from the OSM project. It has a memory saving cache file format which stores several tiles in one file. This is very good for storage on SD-cards which have large block size (since a file always uses at least one block). The cache can be pre-filled easily using one of several available tools.
It can access Google to find addresses and also download and display routing instructions.
GpsMid
GpsMid works completely offline and displays pre-processed OSM vector data. This means the map can be rotated and the display style can be customized. It is possible to search for street names and there is even experimental routing support. Since the default is to store all data in the JAR file, this program is not very useful for phones with a low JAR file size limit (like my phone) without a patch (which is not perfect but pushes up the map size limit quite a bit).
Map Mobile Navigator
MapNav looks very promising. But I haven't tested it extensively yet, due to some compatibility problems with my Bluetooth GPS device. It can also display OSM bitmap tiles. It has many more features than MGMaps, like the ability to show and record GPX tracks.
There are several possibilities to store the maps. The one I find most useful is also to pre-fill the cache folder (the other modes tend to be very slow with large maps on my phone).
Mapping for OSM
If you want to help the OpenStreetMap Project yourself, you can use GpsMid or MapNav to create GPX traces that can be uploaded to the OSM server. One more program you should know about is Mobile Trail Explorer (it can in principle also display map data, but only a very limited area).
GpsMid and Mobile Trail Explorer can create geotagged audio notes. GpsMid can also create geotagged pictures. This is very useful!