Many apps look for authenticated sessions across their other apps to log you in. Google does this too.
On iOS, certain things intentionally survive app deletion, most notably the Keychain. Credentials stored there are not removed when you delete an app, by design. I mean, it is shared with web login, and apps do have associated domains.
I'd have to check if apps can read your phone number, I think they can, that's one of the standard UUIDs for a lot of messenger apps.
And apps from the same group can have a shared set of preferences. Or could: I never needed to add that feature to any app I've worked on, so if it was ever removed (or if I misunderstood the mechanism) I never found out.
Now, back in the iOS 4 (5?) era I did manage to get the horrifying situation where a factory reset(!) device was still getting push notifications for my twitter account (with no app installed), so I won't say nonsense can't happen (and you listed Meta apps, and Meta have a reputation for pushing the limits on exactly this category of nonsense), just that what you're describing isn't a smoking gun.
I checked the "Passwords" and there was no entry for these apps (I think that's the only place for the keychain on ios?).
And it's not about the phone telling its phone number.
Does the iPhone have an IPv6 address that is unchanged between the first app install and 2nd app install?