Just looked that up, and the site describes the project as

> GrapheneOS is a privacy and security focused mobile OS with Android app compatibility

What does that mean? Is it a built-from-scratch OS with an Android compatability layer (like Blackberry 10), or is it just an indirect way of saying they’re based on Android (like Cyanognemod/Lineage OS)?

It's based on the latest Android (AOSP) + privacy/security improvements. From a UX point of view it's basically a vanilla Android without any proprietary Google code (which means no Google Play of course but you can install F-Droid). The main developer is a security researcher and many of his improvements have been accepted upstream to AOSP.

Or even more friendly, CalyxOS. Works perfectly, easy to install and very few problems in the 6 months I've been using it

On which reasonably modern/performant phones can one install them? I did bought an iphone as my latest phone, because Google-riddled android is ridiculous (even though I like the ecosystem much better. Iphones can feel like some embedded software that only allows a few possibilities), but mainly because I could not find a phone on which installing some AOSP fork is safe, won’t delete important firmware (I believe quite a few mobiles will delete proprietary camera firmware)

It's mainly on Pixel phones, ironically. Has something to do with the security chip they come with