Hi @AxolotlGuy! Glad to see another Construct user around here. Are you sure about the release/debug apk? I have a lot of Android downloads and most of them have had no problems installing the APK. Are you using a (rooted) android phone without Google/Play Store?
I always thought that release APKs would work anywhere if they are unsigned, and that debug is just for debugging. I'm pretty sure I used an unsigned release apk, but I might have uploaded a signed one by mistake. That would explain it if you had problems installing without Google/Play Store.