In a residuals vs fitted plot, how do I interpret a homoscedastic variance that is not randomly distributed above/below the line?
This suggests that there's a nonlinearity in your data that isn't reflected in your fitted model.  You haven't told us anything about your predictor variables, but for example if you've fit a model of the form $y=ax+b$, then perhaps you could try adding a quadratic term $y=ax^{2}+bx+c$.