The Standard Model of particle physics and the Lambda-CDM cosmological paradigm have been largely successful in describing the current state of the universe and how this came to be. And yet, we know both descriptions to be incomplete, as there exist a great number of open questions left unaddressed by both. This thesis presents several model building efforts towards resolving these shortcomings in our current picture of particle cosmology. After reviewing the current state of affairs and the puzzles that persist, we turn to the events of the early universe. Focusing on two exceptionally promising probes --- primordial black holes and their accompanying gravitational waves --- we show how constraints on both can lead to inferences about inflation, the subsequent expansion history, and more. Next, we turn to the cosmological phase transitions which may have occurred during this period, with particular emphasis on strongly first-order phase transitions accompanied by gravitational wave signatures. We address a major source of uncertainty in predictions of such phase transitions and present novel theoretical bounds on a model which is in principle capable of making the electroweak phase transition strongly first-order. Finally, we examine three mysteries of late-time cosmology, informed by present day observations and data. First, in the context of dark matter model building, we present a new scheme of asymmetric reheating which can reconcile dark sectors with light degrees of freedom with precision observables. Next, in light of recent observations of supermassive black holes at surprisingly high redshifts, we explore the possibility of supermassive black holes of a primordial origin. Finally, we present a novel mechanism for generating the primordial magnetic fields required to seed the cosmological magnetic fields observed today.