It is our fault in the sense that we selected MySQL for our system, which means we would have this problem where ever we were hosted.
No, we'd only have this problem at places that use the MySQL per-user connection limit as a way of limiting server resource use for shared hosting. Not all hosts do it that way.
Netgate just gives you a CPU/memory limit and you get an error from in your browser if an attempt to load a page exceeds the account limits.
Dreamhost has this conuries system, where you don't have a limit but you pay more a a lot extra if you exceed your allocation. At our rate of use we'd be their favorite customer, but that's another issue.
So moving to another shared hosting situation isn't necessarily going to put us in this situation again, but I think the stress for the stompies would be much less with a dedicated server. They wouldn't have to worry that each small change to the Phoenix code might put them in dutch with the host.