"if Heroku simply spawned a new instance (they're already running on EC2) for each customer, wouldn't this be mitigated?"

Yes, but that'd cost a ton more than what they're doing right now. Consider the number of apps that they are hosting at the free level right now. Offering private instances as an upsell might make some folks happy though.