MacBook Pro takes 10 minutes to shutdown
The first thing I would do is reset the System Management Controller. Do this as follows:


Shut down your MBP
Keep the power cable plugged in.
Press at the same time shiftoptioncontrol (on the left side of the keyboard) and the power button
Let go
Turn your computer back on with the power button.


Once you've done that, test for any differences and report back.

Resetting NVRAM

You mentioned that you reset the NVRAM. Just in case you weren't aware, resetting this on the late-2016 MacBook Pros is different to all other Macs. The correct process is:


Shut down your machine. Yes, a full shut down, not just logging out.
Press the power button and then immediately press the commandoptionpr keys. 
Keep these keys pressed down for at least 20 seconds!
Let go of the keys and let your Mac reboot normally.


Note 1: When you log back in you may need to readjust some of your system preferences (e.g. speaker volume, screen resolution, startup disk selection, time zone information, etc).

Note 2: These steps will also work to reset the NVRAM (or PRAM) for all Macs. However, the late-2016 MBP models actually required the commandoptionpr keys to be held down for 20 seconds, while earlier Macs did not require this, but doing so did not cause any problems either.