We report evidence for the first generation of XUV spectra from relativistic surface high-harmonic generation (SHHG) on plasma mirrors at a kilohertz repetition rate, emitted simultaneously with energetic electrons. SHHG spectra and electron angular distributions are measured as a function of the experimentally controlled plasma density gradient scale length $L_g$ for three increasingly short and intense driving pulses: 24 fs and $a_0=1.1$, 8 fs and $a_0=1.6$, and finally 4 fs and $a_0\approx 2.1$, where $a_0$ is the peak vector potential normalized by $m_{e}c/e$ with the elementary charge $e$, the electron rest mass $m_e$, and the vacuum light velocity $c$. For all driver pulses, we observe correlated relativistic SHHG and electron emission in the range $L_g\in \left[\lambda /20,\lambda /4\right]$, with an optimum gradient scale length of $L_g\approx \lambda /10$. This universal optimal $L_g$-range is rationalized by deriving a direct intensity-independent link between the scale length $L_g$ and an effective similarity parameter for relativistic laser-plasma interactions.