This thesis presents a pair of searches for new phenomena at the Large Hadron Collider using data collected by the Compact Muon Solenoid (CMS) experiment between 2016 and 2018. Both searches employ sophisticated new analysis techniques, some of which are being demonstrated on CMS data for the first time. The first search targets inelastic dark matter, a dark matter model predicting a unique collider signature involving missing transverse energy and soft, displaced leptons. The analysis makes use of novel reconstruction techniques for soft/displaced electrons and muons, and provides some of the first collider-based constraints on inelastic dark matter. The second analysis is a model-agnostic search for new dijet resonances at the TeV scale, and employs state-of-the-art machine learning-based anomaly detection techniques. The results demonstrate good sensitivity to a wide range of new physics scenarios, and constitute an important proof-of-principle for the techniques.