Suppose X is a random variable, such that $F(t) := P(X < t) \in C(\mathbb{R})$. Is there a way to find $\min\{m(|X-c|), c \in \mathbb{R}\}$? Here $m$ stands for median.
I know the solutions for two particular cases: (and they both use a similar method):
If $X \sim U[a, b]$, then $$P(|X - c| < t) = P(c - t < X < c + t) = \begin{cases} 0 & \quad \text{if } c + t < a\\ 0 & \quad \text{if } c - t > b\\ \frac{2t}{b - a} & \quad \text{if } a < c - t < c + t < b\\ \frac{c + t - a}{b - a} & \quad \text{if } c - t < a < c + t < b\\ 1 & \quad \text{if } c - t < a < b < c + t\\ \frac{b - c + t}{b - a} & \quad \text{if } a < c - t < b < c + t \end{cases} $$ That results in $$m(|X-c|) = \begin{cases} \frac{b + a}{2} - c & \quad \text{if } c < \frac{3a + b}{4}\\ \frac{b - a}{4} & \quad \text{if } c \in [\frac{3a + b}{4}; \frac{a+3b}{4}]\\ c - \frac{a + b}{2} & \quad \text{if } c > \frac{a+3b}{4} \end{cases}$$ And that means, that $\min\{m(|X-c|), \:c \in \mathbb{R}\} = \frac{b - a}{4}$.
If $X \sim Exp(\lambda)$, then $$P(|X - c| < t) = P(c - t < X < c + t) = \begin{cases} 0 & \quad \text{if } c < -t\\ 1 - e^{-\lambda(c + t))} & \quad \text{if } c \in [-t; t]\\ 2e^{-\lambda c}sinh(\lambda t) & \quad \text{if } c > t \end{cases} $$ That results in $$m(|X-c|) = \begin{cases} \frac{\ln2}{\lambda} - c & \quad \text{if } c < \frac{\ln2}{2\lambda}\\ \frac{arsinh(\frac{e^{\lambda c}}{4})}{\lambda} & \quad \text{if } c > \frac{\ln2}{2\lambda} \end{cases}$$ And that means, that $\min\{m(|X-c|), \:c \in \mathbb{R}\} = \frac{\ln2}{2\lambda}$
However, I failed to apply this method to the general case.
Not a full solution but an idea that gives useful shortcuts (sometimes).
Imagine the PDF of $X$ as a picture. The the PDF of $X-c$ is of course just shifting, and $|X-c|$ is then folding around $c$.
What is $median(|X-c|)$? Since $|X-c|$ has a definite lower bound at $0$, the median is just the point $m>0$ where the CDF of $|X-c|$ reaches exactly $P(|X-c| < m) = 1/2$. If you "unfold" the picture, this corresponds to points $-m, m$ where:
$$P(-m < X-c < m) = 1/2 = P(c-m < X < c+m)$$
Think of your optimization as running over all $c, m$ values, but subject to the constraint above, and your objective is minimize $m$.
But this is equivalent to minimizing ${b-a \over 2}$ over all possible $a,b$ values, constrained by:
$$P(a < X < b) = 1/2 = CDF(b) - CDF(a)$$
So generically, you can do this: For every $a$, define $B(a)$ to be the value $b$ s.t. $CDF(b) - CDF(a) = 1/2$. Then you find the $a$ which minimizes ${B(a)-a \over 2}$.
However, graphically this view gives you some possibility for shortcuts. You're trying to find a range $(a,b)$, as narrow as possible, which still contains $1/2$ of the probability. So you look at the PDF and in many well-known cases the solution is visually obvious. E.g.
For $X \sim U[a,b]$ it is obvious that any range of width $w = {b-a \over 2}$ which is entirely $\subset [a,b]$ will do. So your minimal $m = {w \over 2} = {b - a \over 4}$ and you actually have a choice of $c$ from the 25% to the 75% point.
For $X \sim Exp(\lambda)$ the PDF is strictly decreasing, so the optimal range must be at the front, i.e. of the form $(0,b)$. You also need $CDF(b) - CDF(0) = CDF(b) = 1/2$, so $b = median(X)$. From wikipedia :) we have $median(X) = {\ln 2 \over \lambda}$, so your minimal $m = {b - 0 \over 2} = {\ln 2 \over 2 \lambda}$
For any $X$ whose PDF is symmetric about its mean, and which decreases monotonically away from the mean, first shift it to zero-mean, then by symmetry your optimal range is $(-z, z)$ which contains $1/2$ of the probability. So you look up $z = CDF^{-1}(3/4)$. In case of $N(0,1)$ you can look this up easily. In case of a triangle or a trapezoid, you do a bit of geometry.
Many "common" PDFs have a single peak and decays on both sides, so the optimal range must include that. Many also have symmetry. Whether there are closed form solutions will depend on the math details but at least you now know where to look. Hope this helps!