Imagine you have molecules that can form spontaneously, like gliders in Conway's Game of Life. You may have several different molecules that are capable of helping to create one another -- an autocatalytic set.
Eventually this could result in more complex chains, and eventually a self replicating molecule can arise.
Imagine slamming a bunch of gliders together to make a machine that replicates more gliders. It's possible! Not likely, but there are so many variables that can influence the environment substantially. It's not like there was a giant homogeneous soup. Parts from over here and over there would form differently and when they meet, amazing things can happen.
In the Game of Life, this spontaneous event is extremely unlikely, astronomically unlikely.
Unlike Game of Life, the real world has a few advantages that improve performance. For one, it's less fragile. Bonds are much stronger and collisions don't cause everything to break. Another advantage is that bonds are attractive: molecules can rotate and turn to snap together strongly. Gliders just explode violently. And finally, the real world is very dense. We're talking trillions of molecules mixing around millions of times per second per microdroplet. Compound that with a few hundred million years... it certainly doesn't feel as surprising as you might expect.
If there were a highly advanced alien race watching earth over a long period of time, it might be interesting, but not unexpected, that suddenly an Eiffel tower springs forth from the surface of the planet, erected by intelligent organisms.
Let's say that you have some RNA soup with some ribozymes some of which weakly encourage some reaction involving other RNA molecules. The occurrence of a cycle of reinforcing reactions might be sufficient to build a crude evolutionary ratchet.
In fact the "cycle of reactions" perspective feels a bit more robust to me since it allows for the proto-replication process to take place over a longer period of time and over larger areas.
Core wars (1984) strongly favored short replicators, so at least in some possible universes complexity growth is not a given.
What's the probability of spontaneous formation across an infinite universe?