With an ever-increasing usage of electronic structure programs by the microwave spectroscopy community, there is a growing need to assess the performance of commonly used, low-cost quantum chemical methods, particularly with respect to rotational constants because these quantities are central in guiding experiments. Here, we systematically benchmark the predictive power afforded by several low-level ab initio and density functionals combined with a variety of basis sets that are commonly employed in the rotational spectroscopy literature. The data set in our analysis consists of 6916 optimized geometries of 76 representative species where high-resolution experimental gas-phase rotational constants are available. We adopted a Bayesian approach for analyzing the performance of each method and basis set combination, employing Hamiltonian Monte Carlo sampling to determine the uncertainty in theoretical predictions of rotational constants and dipole moments. Our analysis establishes a hierarchy of accuracy and uncertainty, with commonly used methods in the rotational spectroscopy literature such as B3LYP and MP2 yielding lower accuracy and higher uncertainty than newer-generation functionals such as those from the Minnesota family, and omega B97X-D, which, when paired with a modestly sized 6-31+G(d) basis, provides optimal performance with respect to computational cost. Additionally, we provide statistical scaling factors that can be used to empirically correct for vibration-rotation effects, as a means to further improve the accuracy of rotational constants predicted from these relatively low-cost theoretical methods. As part of this, we demonstrate that the uncertainties can be used in simulations of rotational spectra to cross-correlate with broadband spectra, a methodology that could be used to quickly and efficiently survey experimental spectra for new molecules.