Time travel is a hard idea to do properly. Lots of people have tried, and many have failed. The trouble is that causality is such a deep part of our understanding of the world (instinctive, I suspect) that we just can't deal with what time travel would do to us. Partly because of this, I suspect that the recordings theory is more accurate than actual time travel in this case.
My theory is that the Almighty's ability to give visions is related to Shallan's memories. Because the Almighty is a Shardholder, he has the ability to Memorize, not a two-dimensional image, but a whole scene in time, including the personalities (spirits?) of the people involved. Just like his taking the memory would be more powerful than Shallan's memories, his ability to play them back would also be extremely enhanced, resulting in what is essentially a three-dimensional interactive world. Just like Shallan, however, he has a hard time placing himself in the scene---changing what he saw would presumably be a lot harder, and putting himself into the scenes means changing one of the participants personalities, suspending the playback, or similar changes. It's harder, and probably requires more time; time he may not have had when he realized Odium was going to kill him.
Notice that the scene in which the Almighty appears himself is not at all interactive. It's setting probably comes from a possible future, so even then it would not be created from complete scratch.