We study the diffusion of Brownian particles with a short-range repulsion on a surface with a periodic potential through molecular dynamics simulations and theoretical arguments. We concentrate on the behavior of the tracer and collective diffusion coefficients D-T(theta) and D-C(theta), respectively, as a function of the surface coverage theta. In the high friction regime we find that both coefficients are well approximated by the Langmuir lattice-gas results for up to thetaapproximate to0.7 in the limit of a strongly binding surface potential. In particular, the static compressibility factor within D-C(theta) is very accurately given by the Langmuir formula for 0less than or equal tothetaless than or equal to1. For higher densities, both D-T(theta) and D-C(theta)show an intermediate maximum which increases with the strength of the potential amplitude. In the low friction regime we find that long jumps enhance blocking and D-T(theta) decreases more rapidly for submonolayer coverages. However, for higher densities D-T(theta)/D-T(0) is almost independent of friction as long jumps are effectively suppressed by frequent interparticle collisions. We also study the role of memory effects for many-particle diffusion.