Lockstep:
Age of Empires II actually used this kind of design in its multiplayer to great advantage. This Gamasutra article -
https://www.gamasutra.com/view/feature/131503/1500_archers_on_a_288_network_.php?page=1gives a great overview of the scheme and some of the problems the development team had to tackle. A design choice of theirs I thought was particularly interesting is that a delay was built into the game so that each machine could maintain a queue of commands to execute, which helped smooth out the impact of latency swings during a session.
As you're probably aware since you're asking a question like this, network design for multiplayer game generally falls on a spectrum that runs from total lockstep to maximum client side prediction. AOE is an example of the former, Halo 2 would be an example of the latter. The two biggest advantages of lockstep are (1) packet size will be much smaller, since you need only describe the inputs to the system, instead of having to describe the state of the system, and (2), development will generally be much easier because lockstep reduces (or in the extreme eliminates) opportunities for desynchronization.
Lockstep's big drawback is responsiveness. Each client machine has to wait until it has all of the inputs of the current frame before it can advance to the next frame. So in the best case the fastest the result of a player issued command can be seen is the round trip latency. Additionally, the inputs of every player have to collated before an update can be issued, so the game can only advance at the pace of the slowest player connection in the session. The slower responsiveness of lockstep ends up determining what game types it's suitable for. Namely, those where instantaneous feedback isn't an important part of the player experience. This makes lockstep a great choice for games like Age of Empires, where the nature of the interface makes the delay unnoticeable, but a very poor choice for fast-twitch games like Halo 2, where the foundation of the player experience is the tight feeling of the controls.
Determinism:
Your biggest enemy with determinism is different floating point behavior on different machines. This Gaffer on Games article gives a good description of the problem:
https://gafferongames.com/post/floating_point_determinism/. It is fairly monstrous. In short, it is not easily achievable to make the same code produce the same floating point results on different platforms. The amount this matters varies with the nature of your project. Inputs into a physics simulation with calculations being performed on multiple machines is basically a no-go (certainly with GM), but if you don't have much interdependence between calculations (unlike a physics simulation) then it might not be such a big deal.
Alternatively, you can ditch floating point numbers all together. Integer-based math can easily be deterministic across platforms. Banks for instance, perform financial calculations on integer values of cents rather than on fractional values of dollars, because it allows complete precision and will give the same results regardless of platform. In the world of games, you can do things like describe player positions using integer values, and as long as your base unit is small enough you have all the precision you need.
Issues with randomness can actually be circumvented fairly easily. Most pseudo random number generators are of a type called a linear congruential generator, which you can read about here:
https://en.wikipedia.org/wiki/Linear_congruential_generator. It turns out they're actually really simple. You could easily build one in GM that produces consistent cross-platform results (as long as you stick with integers).
Reliable UDP:
This also isn't so bad, there are only a few components. To have reliable messaging, the receiver of the message has to respond to the sender with a confirmation that the message was received. If the roundtrip ping time elapses and the original sender hasn't received a confirmation, the sender begins reissuing the same message until that confirmation comes back. To achieve that effect, you need unique identifiers for your messages, a way to store messages that have not yet been confirmed as received, and a way to associate them (easy enough with buffer copies and a ds_map). The recipient also needs to store the id's of messages it's previously received, so that if it receives the same messages multiple times it only acts on it once.
Hope this helps.
Also, this other Gaffer article describes a lot of stuff related to your question. He's even gone as far as using lockstep to produce a cross-network physics simulation:
https://gafferongames.com/post/deterministic_lockstep/ The entire website is a great resource on network multiplayer design.
