Can the 'bin size' in a histogram be thought of as a regularity constraint?
Yes, I think that the idea is to think of a histogram as a particular case of Kernel Density Estimation. In this case, the kernel function for a KDE to be a histogram is an indicator function. In this case, the bin size is equivalent to the bandwidth of the KDE.

The bandwidth of the KDE is indeed a regularity measure: KDEs with very high bandwidth have huge bias (they say that the distribution is uniform), while KDEs with very low bandwidth have huge variance (they adapt to the training data but do not generalize well). As the bandwidth of a KDE is equivalent to the bin size, we can say that the bin size is a regularity measure.