Google maps navigation application is available outside the US via a modded google maps version that allows full turn-by-turn navigation aided by spoken street directions.
I found this on androidcommunity.com. The steps required are:
1. get an app installer from Android market - I use a free app eoeAppinstaller Pro
2. unmount your mini-SD card
3. download modded maps app from here and copy apk file to your mini-SD card
4. re-insert mini-SD card and run installer app.
5. select the maps apk file (long press) to install
6. Voila you now have full google maps navigation installed on your Android handset!
I have this on my HTC Magic 1.6 on vodafone network and it works brilliantly!
See related GZ discussion here.
BTW I love my HTC magic.