But let me ask if you agree that considering Conway's 2D Life world with simply-specified initial conditions as in your example, that conscious life would be extraordinarily rare?
I certainly agree that it would be "extraordinarily rare", in the sense that the size of the lattice would need to be very big, and the number of clock-ticks required would need to be very large. But "big" and "large" are such relative terms! Clearly, our own universe is very, very big. The question is, how can we sensibly determine whether life is more likely in our universe or in Conway's Life universe?
I don't believe we have anywhere near enough data to answer this question, but I don't think it's unanswerable in principle. Fredkin actually believes that our universe is a 3+1D cellular automata, and if anyone ever found such a description of our physics (or some other fundamentally computational description), then we could directly compare it with Conway's Life, determining for each one how big the lattice needs to be, and how many clock-ticks are required, for life to appear with (say) 90% probability. (Of course, this determination might be difficult even when we know the rules of the CAs. But we can try.)
One thing that you'd have to take into account is the complexity of the rules you're comparing, including the number of states allowed per cell. Not only are the rules to Conway's Life extremely simple, but the cells are binary. All things being equal, I would expect that an increase in the complexity of the rules and the number of cell-states allowed would decrease the necessary lattice-size and/or number of clock-ticks required for SASs to grow out of a pseudo-random initial state. I mention this to point out a problem with our intuitions about our universe vs. Conway's Life: the description of our universe is almost certainly more complex than the description of Conway's Life with a simple initial state. If Fredkin actually succeeds in finding a 3+1D CA which describes our universe, it will almost certainly require more than 2 cell-states, and its rules will certainly be more complex than those of the Life universe. We have to take this difference into account when trying to compare the two universes, but we have nowhere near enough data to quantify the difference currently. We really don't know what size of space in the Life universe is equivalent to (say) a solar system in this universe.
In a way, this is all beside the point, since I have no problem believing that one CA can evolve SASs much more easily than some other CA whose rules and initial state are exactly as complex. (In fact, this must be true, since for any CA that supports life at all, there's an equally complex one that isn't even computation universal.) I have no problem believing that the Life universe is, in some objective sense, not very conducive to SASs. Perhaps it's less conducive to SASs than our own universe, although I'm not convinced. What I have a problem believing is that CAs as a class are somehow less conducive to observers than quantum-physical models as a class. In fact, I think it's substantially more likely that there are relatively simple CA models (and other computational models) that are much more conducive to SASs than either Conway's Life universe or our own. Models in which, for instance, neural-net structures arise much more naturally from the basic physics of the system than they do in our universe, or the Life universe.
In many ways, our universe seems tailor made for creating observers.
I understand this perspective, but for what it's worth, I'm profoundly out of sympathy with it. In my view, computation universality is the real key - life and consciousness are going to pop up in any universe that's computation universal, as long as the universe is big enough and/or it lasts long enough. (And there's always enough time and space in the Mathiverse!) When I think about the insane, teetering, jerry-rigged contraptions that we call life in this universe - when I think about the tortured complexity that matter has to twist itself into just to give us single-celled replicators - and when I think about the insane reaches of space we see around us (even if we end up finding life in practically every solar system, there's a crazy amount of space even between planets, not to mention stars) - I find it easy to believe that our universe is just one of those countless universes out there in Mathspace which isn't especially conducive to life at all, but is simply computation universal, so life pops up eventually.
Because of the above conclusions, the problem of measure is a serious one for me. I don't have a clue why I would be more likely to find myself in a universe like this one instead of some CA universe. Regarding your suggestion that we might judge universes not only by the complexity of their rules and initial states, but also by the complexity of the simplest program which "finds" SASs within them: as I understand the proposal, universes (or observer-moments within the universes) which have simple rules and initial states and yet generate SASs easily would have greater measure, because the program needed to "find" these very common SASs would also be simple. This is an intriguing idea, but it doesn't help me, because I don't (yet) see why simplicity or complexity of any kind should affect measure. I can imagine a CA world which is sparsely populated with SASs, and one that's densely populated with them, but the number of SASs (or the number of observer moments) in both worlds seems exactly the same - (countably?) infinite. So why would I be more likely to find myself in one of those universes rather than the other?