When there are differences in timing for deploying, there are a few things to look at:
Are connections being made in the same way (protocol, etc)? You can check by running the following query on both instances:
SELECT *
FROM sys.dm_exec_connections conn
INNER JOIN sys.dm_exec_sessions sess
ON sess.[session_id] = conn.[session_id]
WHERE [nt_user_name] <> N'SQLSERVERAGENT';
Are there any Linked Servers being used? If so, then it's possible that security setup differences between the two instances.
Is the instance-level default Collation the same on both SQL Servers? Database-level default Collation is "typically" in sync, especially if you are using "deploy database properties". Instance-level Collation mostly affects variable names and cursor names, so the idea here is that potentially the schema compare that SSDT does in order to figure out the incremental update, might be impacted.
Are you deploying using the same SSDT Profile & options? Different settings could produce different rollout timings.
Are there any other differences between the two instances?
In this particular case, there was a difference between the two instances: the remote instance is actually SQL Server 2008 R2, not 2016. Also, the instance-level default Collation was different between the two instances.
With that info, I would suggest a few things to try:
In your DB project properties, if the "Target Platform" is set to 2008 R2, then try changing it to 2016 and just deploy locally to see if that makes a difference.
If not, then to test the default Collation thing, create a new instance locally with the same default collation as the 2008 R2 instance
Try installing 2008 R2 Express locally (use the same default Collation as remote instance), and publish to it.
In this particular case, the "Target Platform" was set to "2008 R2", and changing it to "2016" resolved the issue for publishing locally. Of course, it is quite likely that the DDL generated for SQL Server 2016 will cause some errors in 2008 R2, though that could be in just the "create" script and not an issue for incremental deployment scripts. It still might be necessary to enable the "Allow Incompatible Platform" option. If there are issues with "2016" being the "Target Platform" for also publishing to the 2008 R2 instance, then you might need separate SSDT Publishing Profiles.
P.S. I must say, though, that ideally, if the remote 2008 R2 instance is the shared Dev / QA / Production server, then the local instance should also be 2008 R2 so that you are developing on the same environment as you are deploying to :-).