We find evidence for long-range and short-range (ζ=70 Å at 4 K) incommensurate magnetic order on the quasi-face-centered-cubic (fcc) lattices of the monoclinic double perovskites La2NaRuO6 and La2NaOsO6, respectively. Incommensurate magnetic order on the fcc lattice has not been predicted by mean field theory, but may arise via a delicate balance of inequivalent nearest neighbor and next nearest neighbor exchange interactions. In the Ru system with long-range order, inelastic neutron scattering also reveals a spin gap Δ ∼ 2.75 meV. Magnetic anisotropy is generally minimized in the more familiar octahedrally coordinated 3d3 systems, so the large gap observed for La2NaRuO6 may result from the significantly enhanced value of spin-orbit coupling in this 4d(3) material.