Microsoft Excel, 229

[...]generated as colored MS Excel cells[...]

Well, since you asked!

Not golfed:

=LAMBDA(
 d,
 LET(
  rec,LAMBDA(s,h,arr,
   IFNA(
    HSTACK(
     arr,
     SEQUENCE(d,1,2,),
     IF(h>=1,
      s(s,h/2,
       MAKEARRAY(h,h,LAMBDA(r,c,
        IFERROR(
         0.5+0.5/SIGN(SUM(TAKE(DROP(arr,2*r-2,2*c-2),2,2))-2),
         --(RAND()>0.5)
        )
       ))
      ),
      2
     )
    ),2
   )
  ),
  rec(rec,d/2,RANDARRAY(d,d,,1,1))
 )
)(8)

Golfed:

=LAMBDA(d,LET(rec,LAMBDA(s,h,a,IFNA(HSTACK(a,SEQUENCE(d,1,2,),IF(h>=1,s(s,h/2,MAKEARRAY(h,h,LAMBDA(r,c,IFERROR(0.5+0.5/SIGN(SUM(TAKE(DROP(a,2*r-2,2*c-2),2,2))-2),--(RAND()>0.5))))),2)),2)),rec(rec,d/2,RANDARRAY(d,d,,1,1))))(8)

Is 226 characters. We'll cut out 3 because (8) is not part of the lambda definition. However, to get color display we need to add some formatting:

• Conditional formatting set for 3-color scale 0,1,2 for black, white, red, respectively, range set to whole sheet. This requires no typing, but if you want to, it's =$1:$1048576. We'll add 3 for the scale I think.
• Custom number format set to ;;; on the whole sheet. We'll add 3 for this. This hides text
• You can also set the column widths to a more viewer-friendly value, like 2.

Output:

Python 3.12 (with PIL and random), 274 273 bytes

import PIL,random;r,a=random.randint,range
def f(n,L=0):v=PIL.Image.new('1',(n,n));v.putdata(L:=[[[0,r(0,1),1][((t:=L[u:=i*2+j*(m:=2*n)*2]+L[u+1]+L[u+m]+L[u-~m])>=2)+(t>2)]for j in a(n)for i in a(n)if L],[r(0,1)for i in a(n**2)]][L==0]);v.save(f'{n}.png')or n<2or f(n//2,L)

-1 byte thanks to KevinCruijssen

f is a recursive function which inputs image size n a power of 2, and generates a list L of random 0,1 values if no L is provided, then runs itself again with L as an input and n//2 as long as n>1. If given an L, it checks the sum of every block of 4 pixels and creates a new smaller list L accordingly. Each call to f saves L as an .png with PIL before calling f again.

Ungolfed:

import PIL,random
r=random.randint
def f(n,s='',L=0):
    #s is optional save directory
    if L==0:L=[r(0,1)for i in range(n**2)]
    else:
        m=2*n
        L=[[0,r(0,1),1][((t:=L[u:=i*2+j*m*2]+L[u+1]+L[u+m]+L[u+m+1])>=2)+(t>2)]for j in range(n)for i in range(n)]
    t=PIL.Image.new('1',(n,n));t.putdata(L);t.save(s+str(r(0,9**9))+'.png')
    if n>1:f(n//2,s,L)

Here's an example f(1024):

Yabasic, 196 bytes

Program that takes input \$n\$ from STDIN and outputs to a 'grafic' window.

Input n
Open Window 5*n,3*n
Color 0,0,99
Fill Circle 0,0,6*n
While n>.5
For x=1To n
For y=1To n
Color 0,0,0
If ran(2)>1Color 255,255,255
Box 2*x+o-1,2*y-1,2*x+o,2*y
Next 
Next
o=o+2*n+2
n=n/2
Wend

Commented

Input n                       rem   take input
Open Window 5*n,3*n           rem   open a graphics window
Color 0,0,99                  rem   set brush color to blue
Fill Circle 0,0,9*n           rem   fill background
While n>.5                    rem   iter across subimages
For x=1To n                   rem   iter across subimage's x 
For y=1To n                   rem   iter across subimage's y
Color 0,0,0                   rem   set brush color to black
If ran(2)>1Color 255,255,255  rem   50% to set brush color to white
                              rem   draw a rectangle for the current cell
                              rem     of the subimage. Uses the 1px 
Box 2*x+o-1,2*y-1,2*x+o,2*y   rem     border to draw each 2px X 2px cell
Next                          rem   loop
Next                          rem   loop
o=o+2*n+2                     rem   update offset for next subimage
n=n/2                         rem   decrement n by base 2 order of magnitude
Wend                          rem   loop

Example Output (\$n=256\$)

Wolfram Language (Mathematica), 93 bytes

Image/@NestList[BlockMap[Boole[#~Total~2+r[]>2]&,#,{2,2}]&,r=RandomInteger;1~r~{#,#},Log2@#]&

Try it online!

This is a function that takes an input n and returns a list of images. TIO can't display the images, but both the Notebook interface and @wolframtap supports graphical output.

J, 91 bytes

load'viewmat'
[:viewmat[:,.~/[:>:&>(,:~2 2)0:`(?@2)`1:@.(1+_2*@++/@,);._3&.:>^:a:[:<,~?@$2:

Try it online!

Output from the above is show below, since TIO won't produce images.

However, here is a TIO link that outputs the raw matrix data, which is where all the logic is. The image is produced simply by calling viewmat on that.

f 16:

C (GCC), 296 bytes

#define f(I,J,d)for(i=0;i<I;i+=d)for(j=0;j<J;j+=d)
main(N,n,i,j,c){scanf("%d",&N);char m[N][N];f(N,N,1)m[i][j]=rand()&2;printf("P5 %d %d 2 ",N,N*2+(int)log(N));for(n=N;n;n/=2){f(n+1,N,1)putchar(j<n&i<n?m[i][j]:1);f(n,n,2)m[i/2][j/2]=(c=m[i][j]+m[i+1][j]+m[i][j+1]+m[i+1][j+1])-4?c/5*2:rand()&2;}}

Attempt This Online!

Outpus a PGM image.

Since PGM stands for "Portable Gray Map", the output is a grayscale image. The 2 in printf("P5 %d %d 2 " is the maximum gray value, hence there are three possible colors: 0 (black), 1 (50% gray), and 2 (white).

Whit the instruction m[i][j]=rand()&2;, each element of the matrix is assigned a random value (with \$p(X=0)=0.5\$ and \$p(X=2)=0.5\$), hence the pixels are uniformly randomly generated with black and white pixels.

In the compression phase, the (c=m[i][j]+m[i+1][j]+m[i][j+1]+m[i+1][j+1])-4? expression is false if two of the four pixels have value 2 (that is, they are white, and the other two are black).

The value 1 is used only for the background pixels.

JavaScript (browser), 334 bytes

f=
n=>[...n.toString(2)].map((_,i)=>(c=document.createElement`canvas`,c.height=c.width=s=n>>i,c.getContext`2d`.putImageData(new ImageData(new Uint8ClampedArray(Int32Array.from([].concat(...a=[...Array(s)].map((_,x,t)=>t.map((_,y)=>Math.random()<(i?a[x][y+=y]+a[x+1][y]+a[x][++y]+a[x+1][y]-1.5:.5),x+=x))),b=>-1<<b*24).buffer),s),0,0),c))
;g=n=>{m.value=0;m.max=n;a=f(1<<n);h(0);};h=n=>o.replaceChildren(a[n]);g(8)

canvas{width:256px;height:256px;image-rendering:pixelated;}

log<sub>2</sub>n: <input id=n type=number size=1 min=0 max=8 value=8><input type=button value=Go! onclick=g(+n.value)><input id=m type=number size=1 min=0 max=8 value=0 oninput=h(+this.value)><div id=o>

Viewer takes input of log₂n. To use the viewer, choose n, click Go!, then use the second input to select which of the output canvases to insert into the DOM. Because the CSS is fixed at 256 pixels, this limits the inputs to 8; the browser's actual limit is 15.