My experience is that built in Nav systems work pretty well. A phone typically needs cell service. I have been in situations where pandora would not work off my phone because there was no service, yet XMRadio still picked up the music. XMRadio picks either satellite signal or from a terrestrial repeater. Nav uses satellites to pin point location three as a minimum. Having said that there have only been a few instances where cell service was bad in California. However elsewhere might be much worst. To add the system might take a few modules over and above just changing the head unit. The antenna could be relocated for sure.
Take a look at my Build sheet and note that there were options for the stereo system. I agree that XMRadio is different from the Nav System. But they may have been integrated. The Nav system is fairly complex and does involve identifying and attaching to Satellites in the sky to determine location.