Linearity of expectations - Why does it hold intuitively even when the r.v.s are correlated?

For intuition, suppose the sample space consists of a finite number of equally probable outcomes (this is of course not true for all probability spaces, but many situations can be approximated by something of this form). Then $$ E(X+Y) = \frac{(x_1+y_1)+(x_2+y_2)+\cdots+(x_n+y_n)}n $$ and $$ E(X)+E(Y) = \frac{x_1+x_2+\cdots+x_n}n + \frac{y_1+y_2+\cdots+y_n}n $$ which is obviously the same.

Say you have $X$ and $Y$ independent and then you turn up the correlation. Say they're mean zero too, just for simplicity. Then $X+Y$ will still be positive just as often on average as it's negative. It's just that it will be more likely that X and Y are positive or negative together. Thus the mean of $X+Y$ stays zero. However, it does increase the variance since $X+Y$ will tend to be larger in magnitude cause $X$ and $Y$ have the same sign more often.

If two random variables are correlated, wouldn't that affect the average of their sum, than if they were uncorrelated?

Being correlated or uncorrelated matters when we have $\mathsf{E}(XY)$ terms. So for uncorrelated RVs, $\mathsf{E}(XY)=\mathsf{E}(X)\mathsf{E}(Y)$. Obviously, when we consider expectation of sum of RVs, or sum of expectations, no such terms appear. Hence being correlated or not does not change anything.