I'm not remotely a physicist, but I have a few comments, which I will do my best to confine to the limits imposed by my knowledge of my lack of knowledge.

Let us assume that you an all-powerful optimization process, and your goal is to finish an extremely long computation (say, a search for a very large Hamiltonian cycle) in the shortest possible amount of time. You have millions of galaxies to turn into computronium. What is the optimal expansion speed of your computer, considering our current understanding of particle physics, general relativity and thermodynamics?

By "optimal expansion speed", do you mean "maximum possible expansion speed given particle physics, general relativity and thermodynamics (according to our current understanding thereof)", or do you see some reason that a slower expansion would be beneficial to the ultimate goal (or is that the question)?

(Meanwhile, I'll just say that I'd first want to either prove P≠NP or find a polynomial-time algorithm for the Hamiltonian cycle problem. P=NP may be unlikely, but if I were an all-powerful optimization process, I'd probably want to get that out of the way before brute-forcing an NP-complete problem. Might save a few million galaxies that way. Then again, an all-powerful optimization process would very likely have a better idea than this puny human.)

Of all the possible Universes in Tegmark's level IV Multiverse, most don't even have a concept of Time.

I'm not sure if something without a timelike dimension would really qualify as a universe. It's really just a matter of definition, but since every mathematical structure has the same ontological status in Tegmark IV, including, say, the set {1, 2, 3}, a useful definition of "universe" will have to be more narrow than "every element of the Level IV Multiverse" and more broad than "every structure that can result from the laws of this universe".

I'm not sure if we'd be able to rigorously define what structures count as "universes" (and it's not terribly important, being that our definition of the word doesn't impinge on reality anyway), but intuitively, what properties are necessary for a structure to seem like a universe to you in the first place? I'd be pretty flexible with it, but I think I'd require it to have something timelike, some way for conditions to dynamically evolve over at least one dimension.