LineageOS, the successor to Cyanogenmod, runs on a lot of devices and doesn't have the Google services installed.

There's also a fork with replacements for some of the Google services: https://lineage.microg.org/

Many of the custom images you can find on XDA Developers do not require that you install Google Play Services.

CopperheadOS is a good choice if security is a priority.

If you need proprietary apps without using Google, you can install and use Amazon's app store app, and download them from there instead.

You can buy a regular phone that has an active community on XDA forums and flash a ROM without installing google services afterwards.

If you can't do that, some phones just let you disable google services. On others you can try getting root access and then disabling them.

As an alternative (or addition for closed-source apps) to F-Droid I can recommend APKUpdater. It is highly configurable, has multiple apk sources, has search and can install apps from Google Play Store.

The Fairphone 1 was shipped without Google services; don't know about the Fairphone 2.

It's shipped with Google services, but the updater lets you change to without Google services without hassle.

I used an android for almost a year without logging into anything Google.

I can't download apps, but the phone itself works fine, and it came with a bunch of pre-installed apps anyway.

And you're still being tracked in the way described in this article. Google play services just needs to be present on your phone. Doesn't matter if you login or not.