Oooh - speaking of GPS software for phones - I just found
Nav4All - the software is free and works on most mobile phones. You will get data charges, but it looks quite interesting. I've not tried it yet, but I'd guess it'd be a good option to try if you got one of those £25 bluetooth gps modules.