For various games, I have download the .apk onto my phone and it begun the process of installing the app, but before the game starts or any app is actually downloaded, I get a, "app not installed," page.

Any idea as to why this happens? Anything I can do?

This happens sometimes on Android when you try to start an app right after installation, but in fact it's not quite ready yet. Usually with bigger apps on slower devices. Look at the app's icon in the launcher, on newer Android versions there's an indicator when that happens.