While I always have an old school map in the car, it is way better to travel with GPS (Global Positioning System) navigation device. I usually plan my trips before leaving the house using Google Maps, which often gives me routing plans that I haven't previously considered. It is super handy to check for navigation landmarks with Google Streetview so I know what to expect along the way.
For both Android and Apple phones, the best navigation system is the Google Maps app. Android phones can also have the additional functionality of Android Auto, which is can be used without having a complementary vehicle entertainment system, unlike Apple CarPlay. Android Auto can be set to automatically start if you've paired your phone with another bluetooth device (like your car). Android Auto is not necessary to use Google Maps for navigation.
Android Auto and Apple CarPlay work with your phone's built-in capabilities but the GPS and cellular antennas will work better if they are close to the windshield to minimize the Faraday Cage effect of the car's structure. So, even if your car is equipped with Android Auto or Apple CarPlay, you should ideally be using a windshield mount for your phone.
Clamping Windshield Mounts
Magnetic Windshield Mounts
We've used GPS devices for many years and have both Garmin (Nuvi 250) and Magellan (Magellan 3065T-LM & Magellan 5045-LM) gadgets. Hands down, even though the Nuvi 250 is older (~2007), it is a far better GPS that either of the somewhat newer Magellans. The problem with the Magellans is poor routing, which often has us unneccessarily doubling back or taking the long way. The Garmin gives accurate ETA estimates while the Magellans' estimates only become accurate when I'm approaching my destination. I don't have any experience with TomTom devices but they seem to be on par with Garmin.
Magellan's "lifetime" maps is for the expected lifetime of the device: 3 years, see Magellan FAQ. In contrast, Garmin just requires you to regularly update the device to ensure the continuation of its "lifetime" (see Garmin Lifetime Maps T&C). Magellan's PC software for managing addresses and updating software is terrible. TomTom provides free lifetime map updates for the lifetime of the device, which is as long as it continues to support it (see TomTom Lifetime Services).
We use the Nuvi 250 in our daily driver because my wife doesn't like (despises?) the Magellan GPSs. I continue to use a Magellan GPS in my 65 Barracuda because it still functions adequately well as a metric speedometer. The Google Map app doesn't display road speed, which is a disadvantage for older cars with inaccurate speedometers. A nice thing with the Nuvi 250 (unlike either of the Magellans) is that it has a trip odometer function, which is very useful for calibrating odometers and speedometers (see Tire Upgrades).
My parents sprung for GM's OnStar in their Chevy Cruze. It too is terrible for navigation as it has occasionally stopped navigating in the middle of a route. While you can get OnStar to store destinations and contacts with voice recall, the process is cumbersome and not intuitive. Not having the ability to manage destinations and contacts online through your OnStar account is another major shortcoming. ONLY get OnStar if it is super important to you that your car has the ability to summon help in an accident.
Because using a smart phone for navigation requires WIFI at a minimum and ideally several hundred MB of cellular data, it can make sense to buy a standalone GPS device for navigation.
Garmin GPS Devices
TomTom GPS Devices