I was just talking to Mark Taipan and Matt Lape who are working on an indoor navigation project that utilizes handheld computers. Their application allows users to see where they are on a map. Of course the small size of handheld computer displays limits the type of maps you can use. This is even more of a problem for many mobile phones (even smaller displays), which are likely to be the actual devices used in any commercially viable indoor navigation application.
One solution may come from projector phones such as this one. If you had a projector phone you could display a map on the wall and presumably get better resolution, or at least larger characters, than what you can get on a mobile phone display. It would be interesting to see if people would be willing to use such a system.