There are two issues with creating an oxygen atmosphere - getting life that emits lots of oxygen, and waiting for every exposed rock and body of liquid is fully oxidized. We could greatly improve on the first of these, so maybe we could reduce the time from 100 million years to 1 million years. However, global-scale geologic processes take geologic time - causing countless billions of tons of iron to rust isn't fast.
Yep. this is why I mentioned that during the first decades of the project most of the oxygen
would immediately disappear into the planet's geochemistry. However, as you wrote the oxy-
gen would be used to oxidize "every exposed rock and body of liquid", and here would be a
major difference between Earth's history and the situation on a terraformed planet: While on
Earth over millions of years layer after layer of rock was formed and oxidized, on the terra-
formed planet only the uppermost layer of the planet would be exposed and soak up the oxy-
gen immediately, the deeper layers would not be exposed and would therefore take up the
oxygen in a much slower process. So, once the uppermost layer of the planet had been oxidi-
zed, the majority of the oxygen produced by the marine algae would remain in the atmosphe-
re and accumulate there, only a comparatively small part of the oxygen would seep into the
deeper, not exposed rock. The planet could be perfectly habitable even long before the dee-
pest layers of rock have been oxidized, although I would not recommend to the colonists to
dig deep mine shafts.