I figured it out. Thanks for your mentioning garbage collection, John. I reduced the service's -mo (old space) parameter and the service works now. It had been specifying 1 billion - and it's a 1GB RAM machine.
We install that command line everywhere without thinking since we assume machines running our application would have at least 2GB RAM.
It turns out the aforementioned events were unrelated to trying to start our service. Sorry about that.
At least if someone else hits the problem, they'll see the solution here. I don't know if other VA versions would have the same failure signature.