How to detect rectangular images inserted into another image?
In the two positive examples, the rectangular box is &quot;likely&quot; to be noticed visually, notably by the frame, but also the difference of the content inside and outside the box, especially in the color diversity.
However, the compression (if lossy, JPEG_like) may induce local fake edges (quantization of the DC and higher frequency), local noise and fake colors along $8\times 8$ squares.
Hence, I would suggest a local/global algorithms in three steps.

First, estimation: a crude segmentation with closed contours. For instance with geodesic active regions or level sets. The principle is as follows: from a starting contour, the border evolve until it meet a region that either has a gradient (edge) and/or the statistics of the regions on both sides are different enough. Generally they are performered on colored gradient-tensors. Although the contour has some regularity, it is allowed to split and separate into several region. I think the is doable by maximizing the color contrast and allowing sharp edge
Second: model matching. You get a set of connected contours, which can be fitted by Cartesian rectangular boxes. The latter can be probed with your size constraints. One question remains: how to select only one box?
Third: decision/machine learning. Given a set of images, and a training ensemble of negatives and positives examples, you can train a logistic classifier on features related to the inner/outer boxes.
If you cannot learn examples, a distance between the feature-vector of the inner box to the feature-vector of the outer box could provide a quantitative metric related to some probability of having a rectangular image  inserted.