Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals