A Web UI where you can click a button that says "Launch VM" given CPU/RAM/Disk requirements, after a few minutes it returns to you SSH credentials.

Don't use cloud services. Literally, spin up a VirtualBox VM from where the web server is also hosted. Bonus points if you can spin up a VM from another web server.