I am looking forward to changing out my Samsung Galaxy S22 Ultra.
But I am very confused of what to choose, of the many options. Here is some criteria you guys could maybe help me choose the perfect fit from:

1: has to be able to use some android apps still, because of government- & banking applications.
2: the car runs it's own android system, but android auto would be nice to still have.
3: It would be awesome to be able to use the linux phone as a pc as well. I loved the videos I have seen from ubuntu touch, where you just connect to a screen through usb c and you have a desktop environment. That is just awesome!
4: I am kind of pro EU. So if the OS is developed in europe and the phone that supports it from the factory is also EU based, it's a huge plus in my book. Not a deal breaker though. My trusy on USA has just dissapeared sadly.

Hope someone will be able to help me out here! Thank you.

my general answer to this would be PostmarketOS, but it's just personal bias ;)

PostmarketOS is probably the largest one you'll find. It supports a huge range of devices, some better some worse. You might have worse driver support and fewer features on newer devices, because PostmarketOS is focused on using the upstream kernel with minimal patches.

Most other mobile Linux distributions use Halium as a translation layer between the Android core and Linux userspace. More stuff might work, but you're still using the ancient Android kernel and proprietary drivers.

Written from my Fairphone 5 I got yesterday to put PostmarketOS on it.

GrapheneOS is a common choice for Android phones. (It's Android, though. Not a Linux phone distro!)

Supported devices: https://grapheneos.org/faq#supported-devices

Banking app compatibility: https://privsec.dev/posts/android/banking-applications-compatibility-with-grapheneos/

That'd still leave you within the Android ecosystem. And it's fairly easy to install, maintain and operate. Though, the phones currently come from Google. And it's still Android, so ultimately comes from Google.

If you want to avoid Google and Apple entirely, I don't think there are many options except a proper Linux phone. There are some few older(?) smartphones supported by projects like PostmarketOS. But do your homework first. It's an entirely different experience, there's often stuff missing or cumbersome to configure or not available at all. And the camera might suck. It's great he have Linux on phones. But I from my own experience, there are severe downsides for regular every-day life, including banking apps, android auto, push notifications, battery life, etc...

Edit: By the way, the Android compatibility layer for Linux is called Waydroid. Maybe you can look up if your banking apps etc work with Waydroid in the first place. I don't think we have any comprehensive list, so that probably needs to be googled for the individual apps, or tested on a Linux computer.

If you don't mind me asking, where did you get and how much did you pay for your Fairphone 5?

I might be mistaken but I think op wants to replace the android on their Samsung, which would rule out graphene

The way I read it is - they want to replace their phone and buy a new one. In case someone wants to replace the software on a Samsung phone, I don't think there's good options. Samsung phones rarely get good Custom ROMS or anything like that. I think what people do is root them, install Magisk and remove some crapware. But that's basically it. Or you'd experiment with some unsupported repack or early effort at LineageOS with SELinux turned off or something like that. Linux doesn't seem to work either. It's often 10 year old models and most models don't have calls working or wifi and a bunch of other things don't work... I'm not aware of any Samsung with usable Linux support.

Ubuntu Touch will probably have the lowest friction as most things work on it as it reuses the Android drivers.

But on carefully selected devices PostmarketOS or Mobian can work.

I got it used from a local online store. 240 CHF that's ~265 EUR or ~300 USD

Fellow swiss guy apparently. It means I ain’t the only one on Lemmy and the only one interested in Linux phones. We might be 2 in the entire country😅

No, no. I know it isn't possible to boot another linux OS on the Samsung phone, So I will be buying a new phone as well.

I know of Jolla Phone comes with SailfishOS, and Fairphone ships with the option of preinstalled /e/OS

But I have no idea if those are great options. I have no experience with any of the linux options.

/e/ is android AFAIK. Their security is also kinda shit.

I think graphene is the best option on purely practical basis, but if you feel strongly about using a Linux project instead of an android based project, you'll want to look elsewhere.