This is being done with IMSI Catcher detector [1] using machine learning to learn which towers you commonly connect to, then warning you when:

a) a new cell tower ID has suddenly appeared at a specific lat/long when it wasn't there before

b) the encryption/protocol changes or gets degraded

[1] https://secupwn.github.io/Android-IMSI-Catcher-Detector/

Furthermore, since these IMSI catchers are mounted on planes, can't they be detected by the fact that they are moving?

Couldn't a stingray mimic a whitelisted tower? Much like your computer can use a different MAC address at your whim.

Whether alone (with user movement and precise clocking) or in a coordinated group effort, devices might begin to triangulate tower location and check this against historical and geographic data.

It would be a bit ironic, if/when triangulation begins to "work" "in the other direction".

It already is: Mozilla has been building apps¹ that allow users to contribute to a shared database of the locations of cellphone towers and WiFi APs.

The idea is to allow GPS-less devices to find where they are, but it could certainly be used to identify new towers in places which had already been mapped.

EDIT: It seems there's also opencellid.org, which actually allows you to download the full database.

¹ https://location.services.mozilla.com/apps

It is theoretically possible to avoid that via cryptography but I doubt the cell phone protocols include that.

3G provides some cryptographic basis for this, but you might not have a UI on your device to require 3G or to warn you about roaming (which could defend at least against early generations of IMSI catchers).