The three I would recommend are GrapheneOS (being Android based, it will be the closest in app support to standard Android, however Pixels are pretty expensive!), the Jolla Phone (which runs SailfishOS, Linux-based but semi-proprietary, has the best Android emulation out of all the Linux phones due to using Android binary blobs), and Nura supported devices (formerly postmarketOS, uses a close to mainline / mainline kernel, supports Flatpak so you get way more options for Linux native apps!)
I would avoid foldables, they are more trouble than they're worth, and the Pixel ones really aren't too great anyways. GOS only supports Pixels, so I would aim for a used device, perhaps a 9 or 10 series. The "a" lineup are good too if you want bright and fun colours.
The Jolla Phone is pretty cheap, and uses easily replaceable batteries too which is awesome! I've heard a lot of good things about it, and it can run many Android apps well :D
If you want something with Nura, the most well supported devices are the OnePlus 6/6T and the Pocophone F1, which you can find used for very good prices! I have a OP6 and its OLED screen has aged very well, it looks just as good as my daily driver Android device. Nura also supports lots of new devices, like the Fairphones (repairable and supports sustainable materials and fair working conditions!!), even the latest FP6 is getting increasing support. If you want to try out the full mobile Linux experience, go for Nura since you will get the choice of Phosh, Plasma Mobile, etc., as well as Flatpak apps (the self-described "app store for Linux")
If you have the budget to go for a foldable, I would instead move you towards purchasing a used (non-folding) Pixel to run GOS, a Jolla Phone, and a device running Nura (either a Fairphone or an older device that supports it). Foldable prices are insane and it would be a lot more fun if you tried out all three degoogled options :>