Since you already have a method to find the largest rectangle I want to build ontop of this solution. I will however start my suggestion by working out the largest inner square for simplicity. Extending the approach to rectangles comes with a caveat that may or may not be relevant to your data.

Lets say I have a perfect square rotated by an unknown angle, with length L, and I run my own (axis aligned) square finder. This initial sollution L0, based on no initial angle (t0=0), already provides a lot of information about all other possible sollutions. Namely, if my perfect square is rotated by 45 degrees, then I will have found a square with length L0=cos(45) * L. Inversely, if the input square was not rotated, then any other angle t1 I try in the next iteration (0 to 45 degrees because of symmetry) will return L1=L/cos(t1).

The lower bound is less important, but may be used to speed up future searches. The upperbound is what is most important, as it tells where any higher maximum may be. Compared to the function call to locate the largest square, it is hardly any work to pick the next best angle to continue our search. By examining the highest possible solution, we will again exclude many possible solutions.

This strategy is apparently similar to Shubert-Piyavskii optimization (came up when brainstorming with Gemini). Just using t0=0 and t1=45 already guarantees the solution is at most 10% larger. In cases where the data is presumed to resemble a square, this will be a very effective strategy. A perfect circle would be the most ineffective since infinitely many angles would have to be checked.

Now getting back to your problem of rectangles a similar strategy can be used. After finding a rectangle, you can compute lower and upper bounds for other angles. Working out the largest rotated rectangle within another is not too difficult. How much it tells you about all other solutions depends on the ratio between height and width.

It is a bit harder to predict the convergence here. If the actual rectangle is really elongated, then your initial guess will likely have its longest diagonal lie parallel to the shortest sides. In the next attempt you will likely find it. If the rectangle has similar length sides then the behaviour will be similar to the square example described above.

The methods above can be disrupted by annoying data thrown at them. The reasoning behind them is that, once you get close to your solution, they are likely inside the actual solution. If your input resembles a snowflake then good luck.This is just an argument to motivate a maximum number of iterations and possibly a tolerance value. Perhaps it is also a good idea to include the largest inscribed circle for some edge cases.