I recommend Gear Navigator as well. I tried Here Wego first since it's the "free" native nav app. In 3 days of testing with 12-15 trips it froze up every 2 miles at the most.
As it's only a navigation app and not a mapping app, you can only search for a location in sequence and only explore the map while "navigating". The only drawback to Gear Navigator that I've found is minor: it only works within a 100 km (62 m) range. I've almost switched my navigation needs completely to my watch at this point though I still use the phone when I actually need to see a map or explore a location.
If you have an LTE version of the S3 and a cellular connection, you may want Gear Navigator S as it works completely independent of the phone.