How do we know that nuclear decay is truly random and spontaneous?

We don't know anything "for certain" but experimental evidence favors randomness over Newtonian deteminacy for quantum decay phenomena. All we can do is proceed on the basis of our best experimental data to build theoretical models that employ consistent mathematics. To do otherwise would be outside scientific boundaries.

Science doesn't tell us the reason things happen. It provides a way to develop models which predict what will happen. For all we know, Zeus himself personally causes every radioactive atom to decay when he sees fit. Science cannot disprove such a claim.

What we can do is use the scientific method. In the scientific method, we pick a "null hypothesis" which is what everybody expects to happen, and an "alternate hypothesis" which is the interesting thing we want to test. Then we run an experiment and hopefully show that the null hypothesis is highly unlikely, while our alternate hypothesis is good. In the case of this topic, the usual null hypothesis is "radioactive decay is random."

To date, nobody has been able to develop a test which can demonstrate that they can predict the timing of radioactive decays better than random chance. That's not to say there's not some local hidden variable, or a cherub that knocks the atom about to cause it to decay. It just says that nobody has been able to provide such a theory which does better than the "radioactive decay is truly random" theory does.

Doesn't everything in the universe just depend on the starting conditions, arguably nothing is random.

You are thinking in terms of classical deterministic physics which has been validated in dimensions much larger than the quantum mechanical dimensions commensurate with Planck's constant h_bar. Nuclear decays are in the range where quantum mechanics has to be invoked, which is by construction a probabilistic theory.

There are differential equations which give the solutions to quantum mechanical problems, where boundary conditions have to be imposed and the probability distributions are predicted and validated by the data. Individual measurements cannot be predicted , only the probability of finding a value can be predicted.

The randomness of the nuclear decays is due to this quantum mechanical probabilistic underpinning:

A nucleus does not "age" with the passage of time. Thus, the probability of its breaking down does not increase with time, but stays constant no matter how long the nucleus has existed.

P.S. For complicated quantum mechanical systems have a look at this answer of mine