Extreme pressure strongly affects the superconducting properties of "simple" elemental metals, such as Li, K, and Al. Pressure induces superconductivity in Li (as high as 17 K) while suppressing it in Al. We report first-principles investigations of the superconducting properties of dense Li, K, and Al based on a recently proposed, parameter-free, method. Our results show an unprecedented agreement with experiments, assess the predictive power of the method over a wide range of densities and electron-phonon couplings, and provide predictions for K, where no experiments exist so far. More importantly, our results help uncover the physics of the different behaviors of Li and Al in terms of phonon softening and Fermi surface nesting in Li.