The excursion-set formalism provides a key connection between primordial density fluctuations and the abundance of cosmic structures such as dark matter halos and voids, traditionally assuming Gaussian random walks. In this work, we extend this framework to fluctuations whose distribution presents strongly non-Gaussian tails. Such tails are beyond the reach of perturbative approaches to primordial non-Gaussianity based on moment expansion. We address the problem with rigorous, analytical derivations relying on the large deviation principle, suited for the study of rare fluctuations. We derive new first-passage time distributions for random walks with non-Gaussian statistics and obtain updated predictions for the halo mass function. We also study the two-barrier problem relevant to cosmic void formation, leading to a new analytical prediction for the void size function, with improved accuracy on large scales. Our results demonstrate the potential of large deviation techniques as a bridge between inflationary scenarios, often leading to strongly non-Gaussian tails, and late-Universe observables.