Structural phase separation in the form of partially disordered stripes, with characteristic length scales in the nanometer range, is observed for superconducting BaPb$_{1-x}$Bi$_x$O$_3$. The evolution of the superconducting coherence length with composition relative to the size of these stripes suggests an important role of the nanostructure in determining the shape of the superconducting dome. It is proposed that the maximum $T_c$ is determined by a kind of "optimal inhomogeneity", characterized by a crossover from an inhomogeneous macroscopic superconductor to a granular superconductor for which phase fluctuations suppress $T_c$.