Two initial points to start:
Location tracking
If you don't want to be location-tracked, you cannot carry a smart phone, or flip phone with a cell provider contract.
The phone you carry on high frequency intervals is communicating with cell phone towers, constantly, 24/7, establishing its triangulated position with them and confirming its ability to receive calls and to transmit data. The service provider records this location history and may share it in some aggregated or sampled form with third parties that you have never heard of (along with some you have).
The phone of course has a number of hardware components the IDs for which are included in these communications and are unique, so individual physical phones have individual histories. In terms of associating those histories with specific humans, all providers make it possible for third parties to have business arrangements wherein it becomes possible to associate those IDs with specific customer account data- name, snail mail address, etc.
There are numerous third parties that had previously built out historical databases of names, including spelling variants, and snail mail addresses, and turn those into whole family histories- parents, grandparents, siblings, children- along with neighbors and other coarse location associations. Some of these are participating in more granular cell-based location tracking arrangements.
Third parties are sometimes not supposed to use this data for certain purposes, or to save it for an extended period of time, and in general they can be trusted only to completely fail to not use this data or to not save it for an extended period. From time to time these failures and the resulting exposures are egregious enough that they make the news.
(Note that if you also leave wifi on, the same is happening with hot spot providers, who are under even less obligation to not do whatever they want with the observation that MAC address x:y:z comes into range of hotspot 12345 every Friday night at 11pm, etc.)
Google
If in particular you want to not leave a data footprint with google, you cannot own or use an Android product. The Android OS is in frequent communications with Google servers to convey various sorts of telemetry. This happens independently of whether you are using any Google-branded apps.
I have not studied what happens if you use a third party OS on Android hardware. They are all to a degree based on the upstream Android source. My scepticism is that all traces of interactions with Android server infrastructure, under all edge cases and so forth, had been excised, would be high.
If you do not want to leave a data footprint with Google then you also cannot visit any websites, because nearly all of them use Google Analytics.
So, with that background, the specific questions:
Q: if I factory reset my phone, will Google recognize me when I next use it? I presume so, as they have at least a fingerprint of hardware/installed apps/whatever.
A: Yes. Phones have unique hardware identifiers. Those identifiers are not changed with a factory reset.
Q: In any case, if I use the same SIM card, I image they will tie me to the device.
A: There is a difference between the cell service provider- for whom the SIM card services as a unique identifier- and Google- which has its own identity infrastructure based on Gmail accounts. Google servers receiving network traffic that originated from the device then comes to Google from the cell provider egress are able in many cases, though not all, to associate that traffic with a unique account at a cell provider. But Google's identity management is not based on the SIM.
Q: would a new 'phone help? If I did not get a new SIM/'phone number?
A new phone, in order to use the cell network, needs to be associated with an account, and that account has to have an identifiable owner- either a person with a name, SSN and address, or a business with a name, TIN, and address. So as long as you have a SIM tied to an account in your name with a cell provider, your use of whatever physical phone with that SIM will associate telemetry data with that account.
Q: what if I get both a new SIM card/phone number and a new 'phone number simultaneously?
See above. One has to think about the concept of "account" in a different way.
Only LinkedIn - and am happy to use that in private mode, via a VPN.
Neither of these things matters if you are authenticating with LinkedIn. All that's happening in "private" mode is that the permanent cookie LinkedIn wants to save with your browser doesn't get saved. But as long as you authenticate- surprise- they know it's you!
Similarly, VPN makes little difference. Sure, the IP address you seem to be coming from may be the VPN provider's, but many VPN setups are broken and the real IPs are easily leaked. There are also numerous tells in searches and communications on LinkedIn that can inform regarding the location of the account. LinkedIn has relationships with third parties with whom some of this data, at coarse levels of granularity, is shared.
I am willing to make some effort, but not extremis.
This is the most important point to follow up on. What exactly is the concern with location and other kinds of tracking?
At the end of the day, ad targeting, while unpleasant, in the US at least is largely innocuous.
There are plenty of places around the world where tracking of various kinds is not innocuous, and where there isn't even the pretence to various forms of privacy. But usually the concerns in those cases center more directly on various authorities and less on specific companies.
