OK. I got it. I realized that storage_port wasn't actually open between the nodes, because it is using the public IP. (I did find this information in the docs, after looking more... it is in section on "Types of snitches." It explains everything I found by try and error.)
After opening this port 7000 to all IP addresses, the cluster boots OK and the two nodes see each other. Now I have the happy result. But my nodes are wide open to the entire internet on port 7000. This is a serious problem. This obviously can't be put into production. I definitely need cross-continent deployment. Single AZ or single region deployment is not going to be enough. How do people solve this in practice?
