For a series of clusters Pd-n (n=4-309) the average metal-metal bond distance has been determined with an accurate all-electron density functional approach. In contrast to experimental data on supported or ligand stabilized palladium clusters, bond lengths of gas-phase Pd clusters are calculated to increase with size, exhibiting remarkably linear scaling with the average coordination number. To achieve good agreement of extrapolated nearest-neighbor distances with EXAFS data and the experimental bulk value, relativistic effects have to be taken into account in the electronic structure calculations. For the example of Pd55O20, the effect of surface oxidation has been examined, indicating a strong increase of the nearest-neighbor distance.