Good replacement for Google Calendar?

As others have said Nextcloud has a calendar, viewable via the webam or thubderbird (can also use the tasks) and any floss calendar app really on android or even the one installed by default probably.
There are a few orgs that permit creating an account so you can avoid selfhosting. Some like from Framasoft are donation funded.

What I use covers not only calender functionality but also address books:
Server: I recommend Baïkal. It's based on the same calendar and contacts library that comes with Nextcloud. Reliable and powerful. This of course means you have to host this PHP app somewhere. If you prefer to have it as a service, a small rented Nextcloud instance may be easier to get because of it's popularity.
Android: As already mentioned DAVx5 covers the sync function very well. As for the Calender app I like aCalendar+ but many others (maybe even stock calendar, but I've never tried it) should work. For contacts the stock app works here, as do others. One thing to look out for: You now have multiple calendars/address books. Make sure you store your data in the DAVx5 based ones. Check if your apps allow you to actually select them, or even better to make them the default. Otherwise it may look like sync is broken.
Linux: I use Thunderbird which supports CalDAV and CardDAV natively.
I use these for years without problems.

I recently went through the process of separating from Google as much as possible here.
As others have said, Nextcloud or Radical or Baikal are all good calendar server options to self-host
On your Android phone, DAVx5 for syncing CalDAV and CardDAV (which the servers listed above use), ICSx5 for any public Google calendars you want to subscribe to (you can almost always get an ICS calendar file link for those), and Etar to interact with said calendars on your phone.
On your computer, Thunderbird is the easiest way to go. There is also the web interface for whatever server you decide to host. There are other options, too. On Linux, I use pimsync + khal/khard.
Caveats:
In Etar, khal, AND the Nextcloud web UI, I have had lots of trouble with being able to apply updates to calendar events, like a new ICS file containing an updated time or place. The only calendar app I've found that handles this correctly is Thunderbird on the desktop.
Doing things this way separates your email account from your calendar account, which can create some annoyances. Every mainstream mail service these days tightly couples itself with a calendar. For instance, to send invitations for a calendar event that I create on Nextcloud, I also have my email account linked to Nextcloud. You can't do this if you have Proton or Tuta because of their encryption. When I had Proton, I used Postmark to have a send-only email account from Nextcloud to send out invitations.
If you want to subscribe to PRIVATE Google calendars (my partner still has Google, so I need to do this), you need to sync a Google account with each device you want to subscribe to that calendar on. There is no way to add it to one of these self-hosted servers. The way that I handle this is by making a throwaway Google account that is only for subscribing to calendars, syncing that to my phone with DAVx5, and while I could sync to Thunderbird on my computer, I pretty much only use Thunderbird when I need to update a calendar event. So, in my case, I use pimsync. To sync a Google account to pimsync, you need to create a fake "app" using a Google account on the Google Cloud Platform, add the CalDAV API and generate credentials, add your calendar sync account to the allowed testing users, and then add the generated credentials to pimsync. It sucks.
As usual, you can't sync any Microsoft calendars with anything other than Outlook.

Nextcloud is my best pick. Of course, it does much more than calendars, so if you're looking for a calendar service that does only that it may be a bit overblown.
Big pros:
Native WebDAV integration out-of-the-box - which means that you can easily export your calendars through WebDAV URLs in any supported app
Support for importing external calendars
If you also use other Nextcloud products (like mail, contacts or office) the integration betweren them is quite well designed
On Android then I use DAVx5 to synchronize calendars and contacts from Nextcloud with my phone, and Etar as a multi-provider calendar app.

Tutanota calender app. Works offline. Encrypted. Sync with tutanota login so very easy to setup.
Use tutanota webb to view calender on pc. Might work as well with their desktop app(not tried)

I have the Tuta calendar.
- tuta indeed
  
  Same (till today) but then the only way you can access your calendar is in the Tuta apps, and then you can't share appointments with others, invite them, and so on. Bit of a limited option, unless your calendar security/privacy is really important to you.

Proton has a good calendar service but if you want to change color labels you need to be on the more expensive tier - and they don't really tell you that ahead of time. Which p'ed me off so much I moved my calendar to a Nextcloud server instead, which works great. It also got me off Keep, Drive, and I'm working on Gmail.

Radical on the server, Davx5 on the phone to sync, Thunderbird on your desktop. The combination has worked for me over many years.
- Man, I've read this like so many times. So... I just set it up and it's working a treat. I installed radicale via radicale-docker, got it confogured with my user, set it up in Thunderbird and install/configured Davx5 and Fossify calendar (via F-Droid) on my android phone.
  <phew>
  
  Docker for radicale (which is unofficial but they don't offer one, so...)
  https://github.com/tomsquest/docker-radicale?tab=readme-ov-file
  The only thing I might have to get used to is the sync delay with davx5. How often do you have yours setup to sync, if you don't mind me asking?
  
  It is also delayed for me, I just trigger a manual sync every time I made a change...
  
  I don't know, it was always quick enough for me so I never went looking for a setting.

Nextcloud, self hosted. But it is maybe overkill, unless you need it otherwise, for family photo album, docs or such. Davx5 also needed on android. Thunderbird for desktop calendar client. Can recommend etar for android calendar app.

I self-host baikal and use davX5 on android with whatever calendar app i want, and on desktop i use betterbird but you can use any calendar app you want.