We can reduce your problem to solving a linear equation modulo an integer. That way we can avoid functions like Minimize.
If a primitive root exists for the modulus, we can take discrete logarithms of both sides and easily solve for r. This following code finds the smallest positive r such that (base^r - const)/mod ∈ Integers.
HasPrimitiveRootQ[n_Integer?Positive] :=
n < 8 || (OddQ[n] && PrimePowerQ[n]) || (OddQ[n/2] && PrimePowerQ[n/2])
HasPrimitiveRootQ[_] = False;
MinExponent[base_, const_, mod_?HasPrimitiveRootQ] := Module[{g,dlhs,drhs,phi,gcd,r,sol},
g = PrimitiveRoot[mod];
dlhs = MultiplicativeOrder[g, mod, {base}];
drhs = MultiplicativeOrder[g, mod, {const}];
phi = EulerPhi[mod];
gcd = GCD[dlhs, drhs, phi];
{dlhs, drhs, phi} /= gcd;
r = Symbol["r"];
Print["Solving ", Mod[dlhs r, phi] == Mod[drhs, phi]];
sol = Solve[Mod[dlhs r, phi] == Mod[drhs, phi] && 0 < r <= phi, r, Integers]
r == Min[r /. sol]
]
And your example reduces to solving a linear equation mod 3:
MinExponent[10, 1, 37]
Solving Mod[2r, 3] == 0
r == 3