In my hometown's downtown we have large parking towers that provide parking at fairly cheap rates. In the city owned one, the first hour is free. It's actually a lot more convenient than hunting for parking at area X, hoping there is street side parking or a parking lot. We also get a walkable downtown as a result too.

So instead of requiring a business to have parking, ban the creation of parking and mandate the creation of parking towers or lots financed by business property taxes instead. You get denser, nicer downtowns as a result. You can similarly socialize parking in less dense areas by banning business from having free parking lots and making a few city ones instead.