What evidence do we have that it takes a long time, other than that it happened late in history, which we already accounted for? My impression is that there weren't progressively-more-multicellular forms evolving into one another over a very long period of time. The first animals lived possibly less than 700 Mya; complex Ediacaran animals appeared 575 Mya; and by 510 Mya we had ostracoderms, which were surely fully multicellular (i.e. with a germline and complex cell differentiation and organs).

That's on the order of 100 million years for some complexity, and possibly some more tens of millions of years for more. But it's also possible that multicellularity evolved much more quickly, and the animals just didn't evolve larger and more complex forms for a while due to e.g. low sea oxygen levels, not having evolved eyes yet, etc.