This is a neat question and I've thought about it before. Here's what we came up with:
You run your algorithm $n$ times to get outputs $x_1, \cdots, x_n \in \mathbb{R}^d$ and you know what with high probability a large fraction of $x_i$s fall into some good set $G$. You don't know what $G$ is, just that it is convex. The good news is that there is a way to get a point in $G$ with no further information about it. Call this point $f(x_1, \cdots, x_n)$.
Theorem. For all natural numbers $n$ and $d$, there exists a function $f : (\mathbb{R}^d)^n \to \mathbb{R}^d$ such that the following holds. Let $x_1 ... x_n \in \mathbb{R}^d$ and let $G \subset \mathbb{R}^d$ be a convex set satisfying $$\frac{1}{n}\left|\left\{ i \in [n] : x_i \in G \right\}\right| > \frac{d}{d+1}.$$ Then $f(x_1, ..., x_n) \in G$. Moreover, $f$ is computable in time polynomial in $n^d$.
Note that, for $d=1$, we can set $f$ to be the median. So this shows how to generalise the median for $d>1$.
Before proving this result, note that it is tight: Let $n=d+1$ and let $x_1, \cdots, x_d$ be the standard basis elements and $x_{d+1}=0$. Any subset of $d$ of the points is contained in an affine space $G$ of dimension $d-1$ (which is uniquely defined by those points). But no point is contained in all of those affine spaces. Hence there is some convex $G$ that contains $n\cdot d/(d+1)=d$ points but doesn't contain $f(x_1, \cdots, x_n)$, whatever value that takes.
Proof. We use the following result.
Helly's Theorem. Let $K_1 ... K_m$ be convex subsets of $\mathbb{R}^d$. Suppose the intersection of any $d+1$ $K_i$s is nonempty. Then the intersection of all $K_i$s is nonempty.
Click here for a proof of Helly's Theorem.
Now to prove our theorem:
Let $k<n/(d+1)$ be an upper bound on the number of points not in $G$. Consider all closed halfspaces $K_1 ... K_m \subset \mathbb{R}^d$ containing at least $n-k$ points with their their boundary containing a set of points of maximal rank (this is a finite number of halfspaces as each $K_i$ is defined by $d+1$ points on its boundary).
The complement of each $K_i$ contains at most $k$ points. By a union bound, the intersection any $d+1$ $K_i$s contains at least $n-k(d+1)$>0 points. By Helly's theorem (since halfspaces are convex), there is a point in the intersection of all the $K_is$. We let $f$ be a function that computes an arbitrary point in the intersection of the $K_i$s.
All that remains is to show that the intersection of the $K_i$s is contained in $G$.
Without loss of generality, $G$ is the convex hull of a subset of the points with full rank. That is, we can replace $G$ with the convex hull of the points it contains. If this does not have full rank, we can simply apply our theorem in lower dimension.
Each face of $G$ defines a halfspace, where $G$ is the intersection of these halfspaces. Each of these halfspaces contains $G$ and hence contains at least $n-k$ points. The boundary of one of these half spaces contains a face of $G$ and hence contains a set of points of maximal rank. Thus each of these halfspaces is a $K_i$. Thus the intersection of all $K_i$s is contained in $G$, as required.
To compute $f$, set up a linear program where the linear constraints correspond to $K_i$s and a feasible solution corresponds to a point in the intersection of all the $K_i$s.
Q.E.D.
Unfortunately, this result is not very practical in the high-dimensional setting. A good question is whether we can compute $f$ more efficiently:
Open Problem. Prove the above theorem with the additional conclusion that $f$ can be computed in time polynomial in $n$ and $d$.
Aside: We can also change the problem to get an efficient solution: If $x_1, \cdots, x_n$ have the property that strictly more than half of them lie in a ball $B(y,\varepsilon)$, then we can find a point $z$ that lies in $B(y,3\varepsilon)$ in time polynomial in $n$ and $d$. In particular, we can set $z=x_i$ for an arbitrary $i$ such that strictly more than half of the points are in $B(z,2\varepsilon)$.