Phil,
Yes, lots of great philosophical questions at the heart of this stuff. Usually I just point people to Huw Price at this point, but I'll venture a few comments of my own.
Very nice quote about Fermat's principle, but if you'll look closely, the claim that "nature... acts without foreknowledge" is precisely the NSU assumption that the universe is just as limited as us humans.
When you get into words like "predecided", I'll direct you to my discussions concerning the block universe in response to Silberstein, above. The very word "predecided" refers to two different times (its subject and object), and therefore has no physics translation -- the philosophical concept of predecision doesn't make sense in the block universe of modern physics.
As for your excellent question: "The deeper question for me then is to ask how a universe underpinned by predecision can have physical outcomes present as being so seemingly lawless respective to their certainty." I certainly have a few thoughts. At one level, the hidden variables that I'm proposing (and that are necessary in any LSU) answers this to a large extent. Just because it's a block universe doesn't mean that we *know* the block; to the extent it's unknown, it appears probabilistic.
But I've only recently come to realize this isn't the whole story. You can't get all quantum phenomena simply by constraining deterministic fields at two times. And the path I'm going down right now -- departing from deterministic equations of motion, underconstraining the intermediate physics between the LSU constraints -- provides plenty of uncertainty all around. (Although one must also relax the Principle of Sufficient Reason to the point where our universe is just one of many possible solutions to the same ultimate constraints.)
As for that great quote you ended with, you may be surprised to see that we used that very quote to start Ref. [12]. We like the intuition of locality (as defined in that quote), and the LSU allows us to keep it, quantum phenomena notwithstanding.
Best, Ken