Negatively correlated random variables have a lower min than independent ones. Let's say I have two random variables, $X_1$ and $X_2$ that are negatively correlated. Further, let's define $X=\min(X_1,X_2)$. Also, $Y_1$ is iid to $X_1$ and $Y_2$ is iid to $X_2$, but $Y_1$ and $Y_2$ are independent. Similarly, $Y=\min(Y_1,Y_2)$.
It's quite clear that we should have $E(Y)>E(X)$. We should also have $P(Y>X)>\frac 1 2$. More generally, maybe we can even say:
$$P(Y>n) > P(X>n) \; \forall \; n$$
The reason is that anytime one of $X_1$ or $X_2$ is pushed up, the other is pushed down. I've validated this for many particular cases. However, I'm looking at a general proof.

Validation on Coupon collector's problem.
Let's say there are $m$ coupons and each time I collect a coupon, it could be the $j$th coupon with probability $p_j$. Of course, $\sum p_j = 1$.
Let $N_j$ be the number of coupons we need to collect before seeing the first coupon of $j$th kind. $N_1$ and $N_2$ are geometric random variables with parameters $p_1$ and $p_2$. 
It's clear that $N_1$ and $N_2$ are negatively correlated since if $p_1$ is high, it takes away some probability mass from $p_2$. So, if $N_1$ is low, we can expect $N_2$ to be high.
Let $N = \min(N_1,N_2)$. This makes $N$ the coupons needed to collect either a type-1 or type-2 coupon. It is clear that $N$ is geometric with parameter $p_1+p_2$. So, $S_a = P(N>n) = (1-p_1-p_2)^n$.
If they were independent, we would have $S_\bar{a} = P(N>n)=P(N_1>n \;\&\; N_2>n)=P(N_1>n)P(N_2>n) = (1-p_1)^n(1-p_2)^n$.
We need to show $S_\bar{a} \geq S_a$, which is the same as: $(1-p_1)(1-p_2) \geq 1-p_1-p_2$.
$$1-p_1-p_2+p_1p_2 \geq 1-p_1-p_2$$
This is obviously true.
 A: Covariance and correlation are very tricky.  They often suggest things that sound true, and are indeed often true, but are not universally true.  E.g. in your context, here is a counter-example where $E[X] > E[Y]$.
(BTW, you conjectured that $E[Y] > E[X]$ but that has no hope to begin with.  Say all possible values of $Y_1 <$ all possible values of $Y_2$, then $X = X_1, Y=Y_1$ and clearly $E[Y] = E[X]$.  So the most you can hope for is $E[Y] \ge E[X]$.  But as the following counter-example shows, even that can be violated.)


*

*$Y_1, Y_2$ are i.i.d. and take values $\{0, 1, 2\}$ with equal prob $1/3$ each.


*

*$E[Y_i] = 1$

*$E[Y] = \frac19 ( 1 + 1 + 1 + 2) = \frac59$


*$(X_1, X_2)$ are jointly distributed as follows, for some $0 < p < \frac12 < q < 1$ with $p+q=1$:


*

*$(0,0)$ with prob $p/3$

*$(0,2)$ with prob $q/3$

*$(1,1)$ with prob $1/3$

*$(2,0)$ with prob $q/3$

*$(2,2)$ with prob $p/3$

*It is easy to verify that $X_i$ has the same (marginal) distribution as $Y_i$


*$Cov(X_1,X_2) = E[X_1 X_2] - E[X_1]E[X_2] = \frac13 (1 + 4p) - 1 < 0$ since $p < \frac12$
So the precondition (negative correlation) is satisfied.  It remains to calculate:


*

*$E[X] = \frac13 ( 1 + 2p)$
Now for any $p \in (\frac13, \frac12), E[X] = \frac13 (1+2p) > \frac13 (1 + \frac23) = \frac59 = E[Y]$. QED

Further thoughts: Since $E[X_i] = E[Y_i]$ and $Y_1,Y_2$ are independent, the requirement that $Cov(X_1, X_2) < 0$ is equivalent to:
$$E[X_1 X_2] < E[X_1]E[X_2] = E[Y_1]E[Y_2] = E[Y_1 Y_2]$$
So you are basically conjecturing that 
$$E[X_1 X_2] < E[Y_1 Y_2]\implies E[\min(X_1,X_2)] \le E[\min(Y_1, Y_2)]$$
But viewed this way, it hardly seems like a reasonable conjecture at all.  The product of two variables has not much to do with the minimum of the same two variables.  In a sense, there should be a lot of "freedom" to choose pairs of variables (even constrained as you described) so that one pair has the higher $E[\text{product}]$ while the other pair has the higher $E[\text{minimum}]$.  And this ultimately points to the fact that covariance, while suggestive, leaves a lot of freedom between the two variables.
