Android - Which phones have the purest Android?

tl:dr; Google phones have the purest Android. They come with Google apps

In Android ecosystem, phones launched by Google are stock Android (aka vanilla). It's the purest form of Android because Google developed the OS and tightly integrated with the hardware (earlier Nexus and now Pixel). They come with Google apps, you can't avoid them, unless you root your device and uninstall.

If you are looking for a phone that is running Android LineageOS -XDA launched a phone that ran LineageOS /Ubuntu out of box. Such devices are more of an exception to the rule (running LineageOS out of the box, as you mentioned in the last paragraph of the question, though LineageOS doesn't qualify as pure Android)

How about looking for models supported by LineageOS? This is a ROM you can flash to your device, and you can even use it without the Google Apps (or flash them later)

Although they are not included in LineageOS as such due to legal issues,[44] users can flash the normal Google apps, including the Google Play Store and Play Apps, with a Zip package, usually referred to as gapps, while installing LineageOS.

You'll need to make sure that you can unlock your phone's bootloader/root the device (double check before you buy it).

The question has quite deep implications.

Android is not an OS, it is an "ecosystem".

There is Android Open Source Project. This is the "base" of the Android OS.

Hardly usable and you will not find pure AOSP on any factory phone.

Vendors get AOSP and build over it to make some phone firmware that fits their business model (it may as well be useful for the user, but this is completely optional).

Then, there is Lineage OS - a community-built Android OS made for selected phone models. In general, it is built just like the vendors' firmwares, except for not having a real business model and driven more or less by the contributors' understanding of usability.

LineageOS comes without any Google apps (not even Google Play, so you cannot directly get apps from it). But you can use OpenGApps to get either the bare minimum of Google stuff (like "pico" package with Google Play only), something more, or a full-blown Google suite. There are also great sources to obtain open-source apps, such as F-Droid.

Or you may skip this step and use some other means to get apps (a lot of limitations apply).

It's worth mentioning that neither Google nor phone vendors are happy with people installing LineageOS (or other similar packages). This breaks their business model. The process of replacing the phone vendor's software is intentionally made complex and challenging. In most cases, it also voids phone's warranty.

There are also a niche phone vendors that ship phones with LineageOS.