extremum Estimator (possibly tobit?)
First of all, this is not a Tobit-type estimator. A Tobit estimator is a maximum-likelihood estimator, which is based on a full specification of the error distribution. You have only the median specified, so it can't be an MLE.

What can we do? To begin with, note that, for a random variable $Z$, the median of $\max(c,Z)$ is $\max(c, \mathrm{med}(Z))$, which can be proved by using the definition of the median.

Thus, for your problem, you have
$$\mathrm{med}(y|X) = \max(c, f(X,\theta))$$
under the assumption that $\mathrm{med}(\epsilon|X)=0$. A natural extremum estimator would be the minimizer of
$$\frac{1}{n} \sum_{i=1}^n |y_i - \max(c, f(X_i,\theta)) |.$$
You defined the median as the minimizer of $E(|Z-e|-|Z|)$, but this is the same as the minimizer of $E|Z-e|$ without $-|Z|$, so I dropped the "$-|y_i|$" from the objective function.

This is a generalization of Powell (1984), Least absolute deviations estimator for the censored regression model, Journal of Econometrics, 25, 303-325. See the paper for more details including consistency. https://web.stanford.edu/~doubleh/eco273/powell1984.pdf