It seems FindInstance uses different methods to find 1 instance and to find more than one instance.

constraint = {a > 0, b >= 0, c >= a + b, a >= c/4};

Trace[
 FindInstance[constraint, {a, b, c}, Integers, 1],
 _Reduce`LinearDiophantineInstance | _Reduce`ReduceInstance,
 TraceInternal -> True
 ]

Trace[
 FindInstance[constraint, {a, b, c}, Integers, 2],
 _Reduce`LinearDiophantineInstance | _Reduce`ReduceInstance,
 TraceInternal -> True
 ]

LinearDiophantineInstance returns quickly, even on the 9-variable problem. The second call to ReduceInstance in the 2-instance case takes a long time, which is easy to believe given the complexity of the auxiliary system. In the 9-variable case, I only waited a few minutes while, I assume, it was building the argument for a second ReduceInstance call.

I do not know whether there is a reason to use ReduceInstance instead of nested calls to LinearDiophantineInstance, similar to Mr.Wizard's approach. Given that it handles both of the examples, it seems unlikely.

It seems FindInstance uses different methods to find 1 instance and to find more than one instance.

constraint = {a > 0, b >= 0, c >= a + b, a >= c/4};

Trace[
 FindInstance[constraint, {a, b, c}, Integers, 1],
 _Reduce`LinearDiophantineInstance | _Reduce`ReduceInstance,
 TraceInternal -> True
 ]

Trace[
 FindInstance[constraint, {a, b, c}, Integers, 2],
 _Reduce`LinearDiophantineInstance | _Reduce`ReduceInstance,
 TraceInternal -> True
 ]

LinearDiophantineInstance returns quickly, even on the 9-variable problem. The second call to ReduceInstance in the 2-instance case takes a long time, which is easy to believe given the complexity of the auxiliary system. In the 9-variable case, I only waited a few minutes while, I assume, it was building the argument for a second ReduceInstance call.

I do not know whether there is a reason to use ReduceInstance instead of nested calls to LinearDiophantineInstance, similar to Mr.Wizard's approach. Given that it handles both of the examples, it seems unlikely.