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];
    	If[sol =!= {},
    		r == Min[r /. sol],
    		False
    	]
    ]

And your example reduces to solving a linear equation mod 3:

    MinExponent[10, 1, 37]

>    `Solving Mod[2r, 3] == 0`

>     r == 3