Cannot install any APK file due to "Out of Space" misleading error (plenty of space)
What are the permissions on the directories where the software will be installed (and the directories leading up to the installation directory)?

Do the application(s) you are using to install the APK's have the install software right denied?  With LineageOS, this is handled by Privacy Guard.  I use X-plore: try installing it (from Play Store) and see if you can install with it.  With LineageOS, you would be prompted to allow X-plore to install software.  (It may request root privilege too.)  Perhaps you inadvertently denied the privilege earlier to your other programs (though you mention trying with adb)?

My suggestion is to backup and try reformatting the sdcard (or better yet use a new one) with the default filesystem using the built-in system utility.  On my phone, this is handled by System Preferences -> Storage (I believe).  Don't make any further changes, and try to install the APK's.