LineageOS 22

Can anyone recommend a supported phone that is small in size?

Unfortunately most of the older models do not have a way to root them (AFAICT, I've checked in on this occasionally for years). I have a 2017 fire that I was able to get lineage on, but unfortunately it was a mostly broken "test" device. Another 2017 is slightly different and I fried trying to short to ground during the rooting process. I also have 2 slightly newer models that have no root available at all, and are virtually unusable as the stock OS has become so slow (5+ second lag times per tap).

This is an extreme oversimplification in an "Explain like I'm 5" style (terminology might also not be perfectly correct, it's more for illustration of the basic concepts):

Imagine, if inside your phone, there's your main processor named Bob. Bob runs all of your apps, Bob is occasionally stupid and gets hacked, but he means well.

Also inside your phone, is another processor named Alice. Bob can't see her even if he can send messages to her, but Alice can see Bob through a one-way mirror. Alice is also located inside of a concrete steel bunker with no entry, no exit, and UV sterilization of all single-page letters coming in or out after examination by an officer. Alice has a special ID card given to her by Google, which was only given her after Google was satisfied in the security of the bunker.

Google sends super high-secure work for Bob to do. Bob isn't the most trustworthy of fellows; so Google also sends a message asking Alice to report back on whether Bob is doing what he's supposed to. Alice sends her report back to Google with her signature on it. Google trusts that signature, because it previously inspected Alice and the security of her bunker, and knows that as long as Alice is safe and Bob can't harm her, Bob is doing the work intended.

Now, you might say, why not just make sure Bob is stronger? Well, Google tried that, but with people wanting to sideload apps, the needs of developers, security bugs, that's all extremely difficult. Having Alice do nothing but verify and sign in a super secure bunker while accepting various requests for oversight - that's easy, auditable, much easier to secure, and rarely needs change.

Where it gets even stronger is what I would call, for lack of a better word, "progressive lockdown." For example, when Bob is just starting up, Alice can check that he started up from an approved OS (Secure Boot). Once that's happened, the Secure OS might hand Alice a piece of code for the OS that is never allowed to change in the future while the device is booted (Secure Monitor / TEE). Alice doesn't have to run the code herself; just panic if that code ever changes. By doing so, the OS now has super-high-security functions for itself, that can always be changed out through any update, without Alice needing any updates, changes, or expanded attack surface herself. By that point, Alice can be OS-agnostic so it doesn't matter whether it's Bob or Kevin, and could even be a permanent hardware feature that never needs updates... oops, you've just invented TPM / Verified Boot / Titan M.

What, FLOSS systems run on unicorn blood or what?

There is a reason why Pinephone and similar run hot as hell for a couple of hours of uptime only. But Linux laptops also have a terrible track record here. It has nothing to do with privacy, it's purely there to properly save energy.

And come on, Linux Desktop has terrible security, just because no one targets the 3% marketshare doesn't mean that they are safe at all. Especially that security is independent of "proprietariness". You can have, say, an open source PDF reader with a vulnerability - you only need to open a malicious PDF file to have your system corrupted. Putting our heads into the sand is not a good idea.

Yeah, I never got Heimdall to work properly.