Great writeup! My team ran into a similar situation at work.

For the key point of:

If you’re wondering whether Postgres should be keeping its estimates up-to-date, it should! In our case, Postgres automatically updates its estimates after a number of rows are modified, and we just didn’t hit that threshold. Because we never did, Postgres never updated its estimates for our table. We’ve since started looking into tweaking those thresholds. Oh, and the reason Postgres chose different plans in our staging environments was because of the different table sizes, or more precisely, different table estimates.

I'd suggest linking the documentation reference; I believe it may be the Postgres doc on "routine vacuuming" (sorry for not including a link - the platform won't allow me to as a new user).

If there's a single takeaway, it might be "if you add an index to an existing database, run ANALYZE after."