I've been wondering, is there some service that runs an SSH proxy that will automatically spin up a machine when I try to connect, and automatically spin it down after some idle period?

Yelp built something you can run on a server that will do that with Docker containers (https://github.com/Yelp/dockersh) but for you to not pay for it during the downtime, you'd need someone else to provide this as a service to you.