a necessary derivation of that universal physics is a vast quantity of space and time which we can not directly observe

This isn't quite right. The only thing that makes the derivation "necessary" is your adjective "universal." We could just as easily say that there is a supergalactic physics that explains all we can observe,

Physics is generally held to be universal, instead of just 'supergalactic'. For one, there is the multiverse. But in general, the idea is, as I discuss later, to find the most parsimonious explanation for everything. This is the optimal strategy, and universality is a necessary consequence of this strategy. Any other physics or system which does not explain all observations is of course incomplete and inferior.

It would be remarkably bad science to voluntarily choose to sample only one kilobyte from one address out of thousands of terabytes of data and assume that the kilobyte is representative.

Not at all. You seem to be applying the analogy that at the cosmic scale the universe is some sort of probabilistic urn that generates galactic-sized space-time slices at random whim. It is not.

There are an infinite set of potential physics that have widely different properties in regions we can not observe. There are strong reasons why these are all necessarily inferior, by the principle of Ockham's razor and the low-complexity bias in Solonomoff induction.

given any sequence of finite observations O, there is an infinite set of algorithms A that perfectly predict/compute the sequence O.

Right, but who says our observations are finite?

Elementary physics. There are a finite number of humans, the earth has finite mass, finite information storage potential, and we have finite knowledge.

What if important phenomenon, like, e.g., consciousness (cough) turn out to depend on infinitely small particles?

If you want to believe something like this is true before you begin, that consciousness is somehow different and special, then you are abandoning rationality from the start.

There are no privileged hypothesizes and no predefined targets in the quest for knowledge.

What if the fate of the universe in a cosmological sense turns out to depend on what happens over infinitely long periods of time? There is no rule that I know of that says that the Universe is not allowed to clog its equations with infinities.

Sure, infinities are possible, although they generally are viewed to signal a problem in physics when they come up in one's math.

But that's all besides the point: our observations are obviously finite. And furthermore, infinities are not at all an obstacle towards a universal physics.

Physics is concerned largely with finding the minimally complex algorithm that fully predicts O.

A noble goal, but who says that sufficient simplicity to allow for computability is possible?

There is no such complexity limit whatsoever to computability - it is not as if a phenomena has to be sufficiently 'simple' for it to be computable in theory (although practical computability is a more complex issue).

Suppose our universe contains some true randomness beyond its initial seeding?

True randomness comes up immediately in quantum mechanics. This isn't an obstacle to computability, whether theoretical or practical. People unfamiliar with computing often have the notion that it must be deterministic. This is not so. Computation can be nondeterministic and randomness is an optimal strategy in many algorithms.

Beyond that, the randomness in quantum mechanics is typically squashed by the central limit theorem; a vast quantity of non-deterministic quantum events become increasingly deterministic at the macro scale.

while the universe is computable in principle, we cannot perfectly compute even a portion of our universe from the inside?

This is true - we can't perfectly compute very much of our universe from within it, but perfect computation is highly overrated, and regardless this has little bearing on whatever original track we once were on.

I don't mean to suggest that it's implausible that everything is governed by a universal physics

It is trivially true, tautological - it is implied by the very meaning of universal physics.

It sounds to me that you have a mystery (consciousness) that you would like to protect.

I just get frustrated when people assert, without evidence that's apparent to me, that physics will surely explain everything that we might wish to know.

This also is trivially true, and is the main point I have been attempting to communicate. Anything that you could possibly want to know can be explained by some model. This fact doesn't require much evidence at all.

If there is some new series of observations that physical science can truly not explain, then it is physical science which changes until it does explain them.