¿Se puede instalar Windows o Android en un hosting para ejecutarlo a través de Internet de forma gratuita?

Sinceramente te digo, como dice mi compañero es posible pero si quieres usar photoshop o illustrator en remoto ya puedes tener fibra óptica al menos, si no te vas a hartar a esperar. Mi consejo es que te compres un pc sobremesa con buena ram y buena tarjeta gráfica y a ese equipo le montes un Windows en versión Professional o Ultimate y le configures el escritorio remoto o terminal server que es muy sencillo de hacer. Y trabajes con ese equipo en remoto desde donde te encuentres. El tema del ancho de banda seguirá siendo un problema pero al menos el equipo al que accedes es tuyo, puedes acceder a el localmente o remotamente dependiendo de lo que necesites y tus datos siempre estarán en tu posesión. Si calculas los 50 0 60 euros que te cuesta el servidor en cloud al mes, creo que te merece más la pena comprar un pc, gastarte 800€ o 900€, pero gastártelos una vez y tener un equipo tuyo que tu mismo administras.

En cualquier sistema puedes emular los demás, excepto Windows en Android. Todo lo demás es posible. Sin embargo, yo después de mucho probar, veo que lo mejor es usar el sistema que necesites directamente. Lo demás son bobadas y sólo existe para cuando estamos forzados a un entorno concreto.
Los servidores con Windows son x2 más caros por defecto, pero no creo que rente tener un Linux con Wine y que pueda fallar. Por no hablar de la gestión del escritorio, el acceso remoto y demás.
Linux->Wine->Aplicaciones Windows
Linux->Virtualbox/VMWare->SO Windows, Android(x86) y Linux
Windows->Cygwin->Linux vía capa POSIX con cyginw.dll
Windows->Virtualbox/VMWare->SO Linux, Windows o Android(x86, no Arm)
Windows->JDK->Android Emulator
Android->Chroot->Linux Arm (no x86)
Respecto a usar Photoshop en un sistema virtualizado, es posible que dé ligeros problemas de organización de ventanas. Yo nunca he necesitado ponerlo en Linux pero sí he leido varios posts, motivo por el cual sigo con mi Windows (ya que gimp3 se retrasa para el 3045 por lo menos)
Si es cierto que para que vaya fluido necesitas por un lado un VPS o Dedicado POTENTE, y al menos una red ADSL normal o mejor.
Nota: No necesitas un dedicado de 50€. Con un Cloud o VPS de suficientes características puede valer. Si te dan a elegir entre OpenVZ o HVM, elige HVM porque tendrás un mejor y más rápido acceso al hardware.
En Amazon puedes obtener un VPS de 1Gb de ram gratis durante 1 año (free tier).
En DigitalOcean te dan códigos de 5$ y 10$ para que pruebes. (Equivale a 1/2 meses de uso continuado).
En amazon también se puede conseguir un módulo GPU Nvidia y así hacer que Photoshop use la memoria de la GPU y no la ram.

Si, es posible (al menos instalar Windows) pero necesitarás un ancho de banda considerable y un servidor potente si lo que quieres es trabajar de forma remota desde cualquier terminal mediante "Escritorio Remoto".

Para empezar necesitarías contratar un servidor dedicado en una empresa de hosting (un hosting compartido no te valdría, necesitas tener una instancia propia de Windows gestionada y mantenida por ti).

Por ejemplo, en domitienda.com, tienen servidores dedicados cloud Windows desde 55€/mes: 

https://domitienda.com/Cloud/Tarifas 

Con tu servidor Windows alojado en la nube podrías acceder remotamente al escritorio introduciendo tan solo la IP o nombre de host en la aplicación "Escritorio Remoto" (o Terminal Server) y trabajar como si estuvieras localmente en el propio servidor (siempre y cuando el ancho de banda de tu conexión a Internet lo permita).

Instalar Android es posible aunque muchísimo más complejo ya que tendrías que virtualizar el Windows remoto, instalar Android y ver si existe algo similar al escritorio remoto (cosa que dudo).