Another vote for Here Maps. I have used Here (Nokia) Maps in the US, Oz and here in NZ. It works extremely well, the voice turn by turn navigation is very good and the on screen information is very useful showing which lane to use at intersections and which exit to use on the motorways etc.

Before you leave home download maps for the the region you want to use. No data required since they work offline.  However the search function may be more efficient if you have a working data connection especially when looking for places of interest, e.g. service stations, banks etc. The on phone database may not be a quite as up to date as the online database. Also if yo want to use the "Traffic" feature to see what traffic congestion is like you will need a data connection.

I would never bother with a stand alone nav device. No need to carry a separate device, it works even when you're on foot and trying to find a point of interest in a city.

I'd recommend (though not absolutely necessary with the voice turn by turn nav) using a screen mounted or dash mounted holder so you can view the screen and make sure you have a charger for use in the car. Most cars have USB outlets but not all of these USB outlets will charge your phone.