While researching the issue on Google and StackOverflow, people were suggesting a myriad of things. An incorrect version of Solr was the cause for one person, anti-virus blocking requests was the solution to another. Many people were suggesting that the next likely culprit was a license issue. This initially seemed plausible to me — I'd last used this VM before the new year and my license had renewed in the start of the year. So I dropped the newest license file into the installation folder and attempted to install it again, only to receive the same error.
At that point I loaded up https://solr:8983 again and initially got an error saying the page couldn’t be found, however a few seconds later the page reloaded and everything was fine. At that point, I realized it was probably taking too long for Solr to start back up after the script restarted it; I was running this inside of a VM and I didn’t have a lot of RAM allocated to it.
After that I dug through the JSON files for the installation package. Inside of sitecore-solr.json I modified the following line:
"Description" : "Starts the Solr service.",
In my case, changing the PostDelay value to 15000 (15 seconds) was sufficient, though you may need to tweak that further to your needs.
After that I was able to complete the Sitecore 9.1 installation without further issue.