What is known about the complexity of finding minimum circuits for SAT?
Let's assume that one cannot solve SAT much faster non-uniformly than uniformly. That is, there is a TM M solving SAT in time T(n), and the smallest circuit for SAT has size T'(n) that's not much smaller than T(n) (say, $T(n) = poly(T'(n))$ - in particular this holds if the smallest circuit for solving SAT has size $2^{\Omega(n)}$ which may very well be true).

So, you could get an "almost" minimal circuit by just running some canonical simulation of M by a circuit, in time that's basically optimal (as much time as it takes you to write the output). Just for this reason, am guessing there will be no lower bound for this question based on any "nice" assumption. However, I don't know how to go from an "almost minimal" to actually minimal. One way to do so will be to use the fact that finding the circuit up to size $S$ is a question in the polynomial hierarchy, and so you should be able to solve it in roughly $T(T(n))$ time which will be $2^{o(M)}$ if $T(n)=2^{n^{o(1)}}$.