Restricting some users from accessing 'public' SharePoint sites

How many Teams/Sites are you dealing with? Depending on the number, you might be better off making all of the Teams Private and then just adding everyone except contractors to all of the Teams.

When you set a team as Public, I think it is technically giving the "Everyone except external users" access to the associated SharePoint site. I don't think it shows up in Site Permissions either and would have to be managed via PowerShell. Even if you did remove this from site permissions, then you would still have to specify SharePoint site permissions the old fashioned way which could break connected functionality in Teams. 

Teams and its associated SharePoint site permissions are closely integrated. Once you start messing with permissions directly in the site, you can create a lot of unnecessary overhead for yourself as an admin. 

In my opinion, for your situation, I would set the Teams to be private and add everyone as Members except for the contractors. If you have tons of users and teams, then I would look into using PowerShell to add the members to the teams.