I haven't thought this completely through perhaps, but I've often thought one extremely simple regulation that might have a lot of good effects would be this:

ISPs must charge customers per byte transferred. In other words, no all you can eat plans allowed, usage based pricing only. This has the benefit of aligning consumer and ISP goals in the sense that providing fast service allows ISPs to make more money, so they are incentivized to provide high quality service built on high quality infrastructure. If the Internet is not working, they make no money. If it is slow, they make less. On the consumer side, it incentivizes efficient use of bandwidth.

Of course, this is only one piece of the puzzle. The other piece is that most ISPs have a defacto monopoly in their region. Not sure how we can solve this one. This is partially caused by bad decision by municipal governments, industry collusion, and it seems in part by just the nature of running physical utilities to homes and businesses (many regions also have electric, water, sewage, and gas monopolies).