Can I install an OS capable of running Android apps on Linode?
If you want to take the Linux software route, I'd suggest reading through the following Make Use Of.com article which explains how you can quickly install Anbox using Snapd, which is compatible with most of the distributions that we offer such as Ubuntu/Debian, etc.
The custom OS route seems to be a bit tricker. Essentially, you'd want to find the ISO of the OS that you'd want to install, and follow our Customer Distribution steps. Here are a few helpful links to get you started: