To elucidate surface diffusion in the presence of a coadsorbate with superlattice ordering, we consider particle hopping on a square lattice with some fraction, theta (B), of quenched blocking sites arranged with checkerboard or c(2x2) ordering. Behavior for low theta (B) corresponds to diffusion around isolated obstacles, and can be described by exact density expansions. Behavior for high theta (B) corresponds to percolative diffusion along (or sometimes away from) domain boundaries. The connectivity of these domain boundaries is closely related to the existence of symmetry breaking [i.e., long-range c(2x2) order] in the distribution of blocking sites. In some cases, symmetry breaking induces critical behavior for diffusive transport which is fundamentally different from that for the conventional "ant in the labyrinth" problem. Our results apply to recently developed models for CO oxidation, where CO(ads) diffuses rapidly through coadsorbed relatively immobile c(2x2)-O(ads). The characterization of CO diffusion in these systems is key to describing spatial pattern formation.