They are not lying, of course. A well-known advertising company known for its engine[1] has installed a rootkit on it. Of course, this warning is about rootkits Google doesn't trust (either).
If security was the objective, Google could easily improve it without compromising freedom. Let people choose who they trust.[2] Encrypt the OS so attackers can't modify it. Or not telling attackers that there's an unlocked backdoor they can use.
[1] Missing: <s>search<s/>
[2] Technically, Android supports enrolling your own key. But that's optional for device makers and I haven't found any useful documentation. You also still get a warning on boot, this one is yellow.
[3] Replacing it is easy to detect unless you somehow manage to replicate the phone state as it was. Part of that state could even be a kind of reverse password that the phone uses to authenticate itself to it's owner.
I think I got 2 years of updates on my TV, and it's not like I'm going to want to throw it out and get a new one, so I have to put up with outdated software.