Google Maps for Mobile works like a champ on the Nokia S60 devices I have been evaluating and playing with for the last year, but if you wanted to run it on a Windows Mobile device you had to have a Java client and then run it inside the Java utility. Luckily, my T-Mobile Dash does include a Java client and I have had Google Maps running on it for a while now. My buddy Kevin just sent me a note and posted a blog entry on the release today of Google Maps Mobile for Windows Mobile devices. You can visit the Google Maps for Mobile website, download and then install the .CAB file now for your Windows Mobile device. I just installed it on my Dash and like it even better than the Java client because the fonts are cleaner, the navigation is better integrated, and I don't have to go through all those Java midlet authorization screens. You can use it to show traffic status too, which is very helpful for my 2+ hour daily commute in the Puget Sound region. Even though there is a GPS menu option, this functionality only works with Helio devices. I would love for it to work with a Bluetooth GPS connection and hope that functionality is added in the future.
I see there is also a .PRC file for Palm OS 5 devices, like the Treo 680 and 700p, but I do not know if that is something that was just launched too since I no longer have a Palm OS smartphone.
Virtual Earth Mobile is another excellent choice that I use on my T-Mobile Dash, and other Windows Mobile devices, and it has had a client available for over a year. If you have a Pocket PC Phone Edition and a Bluetooth GPS then you should be able to get position location using GPS with this application. Traffic support is not provided in Virtual Earth Mobile though.