New physics in the neutrino sector might be necessary to address anomalies between different neutrino oscillation experiments. Intriguingly, it also offers a possible solution to the discrepant cosmological measurements of $H_0$ and $sigma_8$. We show here that delaying the onset of neutrino free-streaming until close to the epoch of matter-radiation equality can naturally accommodate a larger value for the Hubble constant $H_0=72.3 pm 1.4$ km/s/Mpc and a lower value of the matter fluctuations $sigma_8=0.786pm 0.020$, while not degrading the fit to the cosmic microwave background (CMB) damping tail. We achieve this by introducing neutrino self-interactions in the presence of a non-vanishing sum of neutrino masses. This strongly interacting neutrino cosmology prefers $N_{rm eff} = 4.02 pm 0.29$, which has interesting implications for particle model-building and neutrino oscillation anomalies. We show that the absence of the neutrino free-streaming phase shift on the CMB can be compensated by shifting the value of other cosmological parameters, hence providing an important caveat to the detections made in the literature. Due to their impact on the evolution of the gravitational potential at early times, self-interacting neutrinos and their subsequent decoupling leave a rich structure on the matter power spectrum. In particular, we point out the existence of a novel localized feature appearing on scales entering the horizon at the onset of neutrino free-streaming. While the interacting neutrino cosmology provides a better global fit to current cosmological data, we find that traditional Bayesian analyses penalize the model as compared to the standard cosmological. Our analysis shows that it is possible to find radically different cosmological models that nonetheless provide excellent fits to the data, hence providing an impetus to thoroughly explore alternate cosmological scenarios.