JavaScript (ES6), 354 352 345 342 bytes
I/O: matrix of integers.
This is quite long but pretty fast -- at least with those test cases.
m=>m[b=P='map']((r,h)=>r[P]((_,w)=>(M=m.slice(~h)[P](r=>r.slice(~w)),a=~w*~h,g=(x,y,F)=>a>b|q.some((r,Y)=>r.some((v,X)=>~v?v^m[Y][X]:![x=X,y=Y]))?0:1/y?[...P+0][P](z=>(F=k=>!M[P]((r,Y)=>r[P]((v,X)=>k^1?q[y-Y][x-X]=v|k:(z|=~(q[y-X]||0)[x-Y],T[X]=T[X]||[])[Y]=v),T=[]))(1)&T.reverse(M=T)|z||g(F())|F(-1)):(o=M,b=a))(q=m[P](r=>r[P](_=>-1)))))&&o
Try it online!
How?
Whatever the tiling is, it is guaranteed that each corner of the matrix is also a corner of the tile that we're looking for. The two outer map() loops extract each possible tile \$M\$ from the bottom-right side of the input matrix \$m\$ and compute its area \$a\$.
m.map((r, h) => // for each row r[] at position h in m[]:
r.map((_, w) => // for each value at position w in r[]:
( //
M = // build M[]:
m.slice(~h) // keep the last h + 1 rows of m[]
.map(r => // for each of them:
r.slice(~w) // keep the last w + 1 columns
), //
a = ~w * ~h, // area = (w + 1) * (h + 1)
... // attempt to do a tiling with M
) //
) // end of map()
) // end of map()
We build a matrix \$q\$ with the same dimensions as \$m\$, initially filled with \$-1\$.
q = m.map(r => r.map(_ => -1))
At each iteration of the recursive function \$g\$, we look for the position \$(x,y)\$ of the last cell in \$q\$ still set to \$-1\$, going from left to right and from top to bottom.
By definition, this cell has either a cell already set or a border on its right, and ditto below it. So it must be the bottom-right corner of a new tile, such as the cell marked with an 'x' below:
Simultaneously, we test whether there's a cell in \$q\$ whose value is not \$-1\$ and is different from the value in \$m\$ at the same position. If such a tile is found, we abort the recursion.
q.some((r, Y) => // for each row r[] at position Y in q[]:
r.some((v, X) => // for each value v at position X in r[]:
~v ? // if v is not equal to -1:
v ^ m[Y][X] // abort if v is not equal to M[Y][X]
: // else:
![x = X, y = Y] // set (x, y) = (X, Y)
) // end of some()
) // end of some()
If all cells of \$q\$ are matching the cells of \$m\$ and the area of \$M\$ is less than (or equal to) the best area found so far, we update the output \$o\$ to \$M\$.
Otherwise, we invoke the following code 4 times:
F(1) & T.reverse(M = T) | z || g(F()) | F(-1)
The behavior of the helper function \$F\$ depends on the parameter \$k\$:
- If \$k=1\$, it computes the transpose \$T\$ of \$M\$ and checks whether all cells in \$q\$ between \$(x-w,y-h)\$ and \$(x,y)\$ are set to \$-1\$. The result of this test is saved in \$z\$.
- If \$k\$ is undefined, it copies the content of \$M\$ to \$q\$ at \$(x-w,y-h)\$.
- If \$k=-1\$, it cancels the previous operation by restoring all updated values to \$-1\$.
It is defined as follows:
F = k => // k = parameter
!M.map((r, Y) => // for each row r[] at position Y in M[]:
r.map((v, X) => // for each value v at position X in r[]:
k ^ 1 ? // if k is not equal to 1:
q[y - Y][x - X] = // set q[y - Y][x - X]
v | k // to v if k is undefined, or -1 if k = -1
: // else:
( z |= // update z:
~( q[y - X] // read q at (x - Y, y - X)
|| 0 //
)[x - Y], // set z if it's not equal to -1
T[X] = // compute T by writing v at the
T[X] || [] // relevant position
)[Y] = v //
), // end of inner map()
T = [] // initialize T to an empty array
) // end of outer map()
Therefore, the code block mentioned above can be interpreted as follows:
F(1) // compute the transpose T[] of M[] and test whether
& // M[] can be copied at (x-w, y-h) in q[]
T.reverse(M = T) // reverse T[] and assign it to M[], which means
| // that M[] has been rotated 90° counterclockwise
z || // if z = 0:
g(F()) | // copy M[] to q[] and do a recursive call
F(-1) // restore q[] to its previous state
