A lot depends on what kind of phone you have. Many privacy-oriented ROMs are specifically designed for Google Pixels. If you don't have a Google Pixel (which I deduce from your search for alternatives to GrapheneOS), I recommend installing any ROM that doesn't come with pre-installed Google Services. Among popular ROMs, I suggest LineageOS or VoltageOS (which I personally use due to its interesting features not present in LineageOS). If you're looking for something built with privacy and security in mind, I recommend DivestOS (a fork of LineageOS).

Regarding installing apps on an Android without Google Services and the Play Store, there are two popular alternatives: F-Droid - This is a store where you can find open-source applications. Aurora Store - It's an open-source client for the Play Store that doesn't require Google Services for operation and doesn't require logging in.