In our city of 500k (which is arguably small, but honestly I think it's the perfect size) we never have to look for a spot. There's always free parking available.
A great example of this is the size of parking lots for sports stadiums.
There's also several stories (I believe SimCity might be one?) of video game developers attempting to make representations of places in their game - and then removing all the parking lots as they realized it would make a boring experience.
My city is less than half of that size. It's impossible to find a parking spot and parking is only free on Sundays.
To make more parking, they'd have to tear down buildings or take away roads. Combined with a poor bus system, it ends up being a bad experience.
I'd much rather have a better public transportation system in my city, it'd be much easier than having to tear things down. More people in the city are pushing for this, so hopefully it'll get better.
