My quest for the GPS device still continues. The latest device that I am thinking about is Fortuna GPSmart Bluetooth GPS Receiver. This one can work standalone as many others, but can also connect via Bluetooth to many other devices. One of these devices can be my SonyEricsson P800. Such a combination can boost the application horizons increadably. Here is a place to buy this device for about $180 USD. Here is a forum (in Russian) where people discuss this device together with P800. And here is another Russian forum with general GPS topics.
Some more GPS related links are here. These are all in Russian, but not all the places where they lead to. There are a number of GPS map repositories out there.