Google Play Services

You can get Google Play Services by installing GApps from here: http://opengapps.org/

There are plenty of guides if you get stuck, is there another reason you're put off by flashing GApps? Hell, I can help you through it myself.

After installing the latest version from apkmirror, and checking I had the Google Framework installed, apps still crashed

You can't simply get Play Services work by installing .apk file(s). Google Play Services (GMS) and Services Framework (GSF) need some extra privileges which normal apps don't have. That's why we flash GApps through custom recovery which modifies some files in /system partition. Other than the .apk files placed under /system/app and /system/priv-app, here is a minimal set of files under /system which are added or replaced. You can see the contents of configuration files to know more about what elevated privileges Google apps have over normal apps.

etc/default-permissions/default-permissions.xml
etc/default-permissions/opengapps-permissions.xml
etc/g.prop
etc/permissions/com.google.android.dialer.support.xml
etc/permissions/com.google.android.maps.xml
etc/permissions/com.google.android.media.effects.xml
etc/permissions/privapp-permissions-google.xml
etc/preferred-apps/google.xml
etc/sysconfig/dialer_experience.xml
etc/sysconfig/google-hiddenapi-package-whitelist.xml
etc/sysconfig/google.xml
etc/sysconfig/google_build.xml
etc/sysconfig/google_exclusives_enable.xml
framework/com.google.android.dialer.support.jar
framework/com.google.android.maps.jar
framework/com.google.android.media.effects.jar
lib64/libjni_latinimegoogle.so

Is this issue caused by not having the Google Play Store installed?

No. Play Services should work fine even without Play Store. Play Store is a Google's privileged app that won't work without Play Services. On first boot after flashing GApps, you can uninstall Play Store. But some apps which are dependent on Play Store can break, such as which make use of License Verification or In-app Billing or possibly other things (I'm not a developer).

Would I be able to flash GApps on a stock ROM?

Theoretically you can flash GApps to any ROM, unless the ROM is deliberately customized not to work with Google's APIs.

the last time I tried to remove the Play Store I couldn't find its package in the /system folder.

Play Store's package name is com.android.vending and app name is usually Phonesky, installed under /system/priv-app. If GApps are uninstalled, Play Store can be re-installed or uninstalled anytime as a user app.

When I tried to flash GApps, it displayed that I already had Google Apps installed

OpenGApps' installer script looks for some files /system/priv-app/GoogleServicesFramework/GoogleServicesFramework.apk and /system/etc/g.prop etc. to figure out if GApps are already installed on device. You can rarely expect a stock ROM from OEM without Google Mobile Services (GMS).

it output Error 70: insufficient memory in system partition

It's also one of installer script's pre-installation check. Check your /system partition what fills it, may be It's stock ROM taking all space. It's possible because they are usually full of bloatware. Remove some unnecessary system apps or move them to /data as user app before flashing GApps. OpenGApps Pico Package will hardly take 200-300 MBs, you can check yourself. Also consider limiting installation size using gapps-config.

is there any risk of crashing my OS

Risk of OS crashing is raised to much higher level when you unlock your bootloader and start playing with the things you are not supposed to. But usually following proper guides, you won't get harmed. Related: Why Android devices are more brickable than PCs?

PS:

Android is a look but don't touch kind of Open Source project. They have very cleverly integrated their proprietary closed-source apps and services in AOSP by tying up OEM's in Compatibility Test Suite (CTS), after all it's one of their biggest revenue source ^{(1, 2)}. Even on a custom ROM, user has to Register the device with Google in order to use GApps, as @Robert has mentioned in comment. They have left no escape way; what one would do with an Android device without Google Play services location APIs (for High Accuracy) and online Contacts backup, just to name a few.

There are a number of Google API's including Analytics, Ads, Authentication, Location, SafetyNet, CloudMessaging and many more. All core GApps (including Play Store) work in collaboration to provide access to these APIs when an app needs to. Many Google and non-Google apps are dependent on these APIs. So if you want to ensure availability of these API's on your device, but are concerned about privacy and want to get rid of Google's closed-source services, consider using microG, a FOSS project but with some limitations. There are also safe ways to access Play Store, Aurora Store is one of them.

RELATED:

• What is the exact functionality of Google Play Services & Services Framework?
• OpenGApps