SSMS can't connect to Azure database
Update: I found that connecting to AWS failed too which led me to yet another Google search which led me here: https://www.sqlservercentral.com/Forums/1891503/Unable-to-connect-to-SQL-2008-Servers-from-SSMS-2017 

Following the instructions from the last post in the referenced site, I downloaded IISCrypto and enabled all of the Ciphers. Bingo.  

https://www.nartac.com/Products/IISCrypto/Download

I'll leave my previous answer below in case it brings comfort to anyone who went through sleepless nights and a couple of keyboards.



Old Update - After installing SSDT 15.8.2 the solution below stopped working for me :(



After days of:


MS Azure SQL Support - not helpful (they just referred me to this post. The one I made.)
Uninstalling SQL Server Express/Developer and three different versions of SSMS - all with the same results
Creating a VM on my computer with Win 10 Pro - SSMS worked on it no problem
Wiping the computer and starting from absolute nothing (using the MSI recovery) - still same issue
Inspecting TLS packets to ensure version 1.2 - it was 1.2
Trying to connect with SqlPackage.exe - never worked for me, same error as SSMS
Trying to connect with SQLCMD - it worked!
Trying to connect with SQL Native Client - also worked!


... I did finally get it to work. Good news is that it works. Bad news is that I don't know exactly why. 

I currently have a fresh Win 10 Pro install with SSMS 17.9.1. I do not have any SQL Server instance installed. My default Windows Firewall is enabled and Norton AntiVirus is managing it (default with the computer). All Windows Updates have been applied as of this writing. I also downloaded and installed the SQL Server 2012 Native Client https://www.microsoft.com/en-us/download/confirmation.aspx?id=50402

When it started working, I had just used SQLCMD and connected to the Azure SQL Server master database and was querying the sys.event_log table. Immediately before that, I had used SQLCMD to connect to a different database on that same server. When I didn't see anything in the sys.event_log table I went back to SSMS and it worked for all of my servers (we have three). 

TL;DR Connect with SQLCMD for a while and see if that helps??