I think this is true, and it should have an elementary (if tedious) proof. I'll discuss the easiest case explicitly; I believe the others could be dealt with in the same way, but I haven't worked out the details and will leave this to the proverbial "reader."

First of all, by translation invariance, we can assume that $x=0$; I also want to relabel $s=1-t$. We then want to show that
$$
d(sy,E) \ge (1-s)d(0,E)-sd(y,E^c) .
$$
This is trivial if $0\in E$, so we can assume that $0\notin E$ and are then left with the cases: (1) $y\notin E$; (2) $y\in E$, which splits into the subcases (a) $sy\in E$, (b) $sy\notin E$.

In case (1) the claim becomes $d(sy,E)\ge (1-s)d(0,E)$. This holds because $d(0,E)$ is the radius of the largest ball about $0$ whose interior is contained in $E^c$, and if we now take the convex hull of this ball and $y\in E^c$ then we see that $E^c$ contains a rescaled ball about $sy$ that gives the desired inequality (clearest from a picture).

This procedure (translate the distances into balls that are contained in $E^c$ and fool around with those by taking convex hulls) should work in all cases. The ugliest case is (2)(b) because now the inequality has three terms. I suggest to proceed as follows: interpret $d(0,E)$ as above (existence of a ball about $0$ that is contained in $E^c$). Then parse $d(y,E^c)$ as "there's a point of $E^c$ within that distance of $y$," and then take the convex hull of this point and the ball from the previous step. If $d(y,E^c)$ is small, this will show that $E^c$ contains a ball of a certain radius about $sy$ (thus bounding $d(sy,E)$ from below, as desired). If $d(y,E^c)$ is large, the RHS becomes negative and we're not claiming anything. Let's just hope this gives the bound as claimed in this case also.