The cosmological constant problem is arguably the deepest gap in our understanding of modern physics. The discovery of cosmic acceleration in the past decade and its surprising coincidence with cosmic structure formation has added an extra layer of complexity to the problem. I will describe how revisiting/revising some standard assumptions in the theory of gravity can decouple the quantum vacuum from geometry, which can potentially solve the cosmological constant problem. I will then argue that a possible fascinating outcome of such a theory is to relate black hole formation to cosmic acceleration, providing a possible solution to the cosmic coincidence. A diverse range of experimental/observational probes over the next decade will tell us whether we are close to the end of this century-old mystery, which in turn could shed light on the nature of quantum gravity and black holes.