Do you have antivirus on your phone? My AV copies the apk after scanning it, then install from the copy. This increases the resource requirements for free space, RAM and processor speed by what seems like double. I get around this by long-pressing the apk and choose to open it with Android package installer, not AV package installer. Has worked for me on every game that initially refused to install.