Currently, my contacts are stored in the Google Contacts app. As I plan to gradually stop using Google services, I am looking for an alternative. Such apps, even though they are among the most important ones, are not covered at all on PG.
Are there any recommended apps? It should be cross-platform in the best case, but it’s optional.
I just use the native contacts app and back-up by exporting as .vcf. Since I rarely need to update my contacts list, storing them locally works for me. If I were to get an iPhone, I would just import the .vcf. If I need to sync my contacts, I would use DAVx5 and sync to my Nextcloud. If you can’t use DAVx5, you can try Tuta, but I haven’t tried this myself.
Proton mail has a very underwhelming contact feature that I use.
I don’t use it myself, but it looks like it can’t be synced with your local contacts.
no you cant, and I personally prefer they dont as contact storage on phone are like opened books for apps.
I would prefer they create a dedicated contact app with dialer function.
I use the default contacts app in GrapheneOS. All contacts are also recorded in Notesnook.
I see Fossify Contacts recommended quite a bit. Maybe give it a go
I self-host a service called Radicale that supports storing calendar and contacts, then use an app called DAVx5 to sync.
I am pretty familiar with self-hosting services, and while it isn’t difficult, it can be somewhat daunting at first.
I personally avoid using default contact app as it relies on contact storage, which is accessible by other applications if permission is given.
I do this to avoid myself making mistakes. I am exploring Fossify contact but it’s automatic backup could only access download folder, which is not covered by my filesync (by synology drive and proton drive), so I am still shopping around. 
I as many others here use DAVx5 and sync it to my Nextcloud instance.
I’ve been using almost the entire Fossify set for a long time, and I’m very pleased.
I keep a close eye on permissions and only grant the bare minimum to any app.
Not going back there as it seems fragile. My setup with TrueNAS + Radicale + Tailscale seems to be working nicely with DAVx5 on my GOS phone and Fedora Calendar+Evolution over on desktop.
What is the problem?
Same here, I just prefer to eliminate the possibility altogether.
I have a free Tuta email account that I only use for contacts
I’ve given up on storing contacts anywhere other than locally on my phone. I back them up biweekly. I thought about it for a while and decided I don’t need sync if it means storing them as plain text on some server. Previously I tried everything under the sun, and as usual, low-tech solutions often turn out to be the best