Regarding relativity, the issue is subtle, so I don't know if this is exactly right. Also, terminology varies, for example "causality" is sometimes taken to mean no superluminal siganalling, and at other times it is taken to mean relativistic causal structure.
First, surprisingly, relativity itself permits nonlocality in the sense that from an operational point of view, a theory can be viable for making predictions as long as it does not allow you to signal faster than light. In fact, the constraint of no faster than light signalling allows more nonlocality than is present in quantum mechanics:
http://arxiv.org/abs/quant-ph/9709026. So if we take the wave function in quantum theory as real (FAPP), then the collapse is clearly nonlocal. However, the collapse does not allow faster than light signalling of classical information, so quantum theory is viable as a relativistic theory, eg.
http://arxiv.org/abs/1007.3977.
So nonlocality and relativity are compatible. What about the Bell inequalities then? There it is relativistic causal structure that is ruled out - no theory that respects relativistic causal structure can explain the nonlocal correlations of quantum mechanics. So relativistic causal structure is a tighter requirement than no faster than light signalling of classical information.
How about Lorentz covariance - can we have a theory that is nonlocal, lacks relativistic causal structure, does not allow faster than light signalling, and is also Lorentz covariant? I don't think there is anything that rules that out, but I don't know how far such a theory can be taken. The issue is discussed in eg.
http://arxiv.org/abs/1111.1425 and
http://arxiv.org/abs/1412.6723.