The minimal surface equation is uniformly elliptic, at least in the sense that its linearization at any solution is uniformly elliptic. It will be convenient to rewrite the equation as 
$$\nabla \cdot \left(\frac{\nabla u}{\sqrt{1 + |\nabla u|^2}}\right) = 0$$
(this is the standard way that the equation is written on euclidean space, anyways). We now have the coefficient $A_{ij} = (1 + |\nabla u|^2)^{-1/2} \delta_{ij}$, and the PDE is $Pu := \nabla \cdot (A\nabla u) = 0$.

By elliptic regularity, the solution $u$ is smooth, so there exists $\varepsilon > 0$ such that on $B_{3/4}$ (say) we have $|\nabla u| < \varepsilon^{-1}$. On $\{|\nabla u| < 1\} \cap B_{3/4}$ we have $A_{ii} > 1/10$, and on $\{|\nabla u| \geq 1\} \cap B_{3/4}$ we have $A_{ii} > \varepsilon^{1/2}/10$. Therefore $P$ is a uniformly elliptic operator and we can apply the usual proof of Harnack's inequality.

EDIT: I guess this doesn't answer the question of whether we can remove the dependence of $C$ on the ellipticity constant. The answer is no, $C$ must depend on the ellipticity. I don't have an explicit example using a minimal surface, but you can already see why this is problematic by taking $(au')' = 0$ on $(0, 1)$. Clearly this is equivalent to the PDE
$$au'' + a'u' = 0$$
and we can take $a(x) = x^2 + \delta$. Then the solution to the equation is 
$$u(x) = \delta^{-1/2} \arctan(\delta^{-1/2} x)$$
which is positive on $(0, 1)$, and for $\delta$ small is approximately arbitrarily well by $x/\delta$. Thus the Harnack inequality, taken say in $(1/4, 3/4)$ becomes arbitrarily bad!