Mathematically, there are two ways of "translating" "I like neither chocolate nor vanilla" (the two ways are logically equivalent, an instance of de Morgan's laws). You can write either:
$$\neg\bigl(\mathrm{like}(\mathrm{chocolate})\bigr)\ \&\ \neg\bigl(\mathrm{like}(\mathrm{vanilla})\bigr)$$
(that is, "I don't like chocolate and I don't like vanilla") or as
$$\neg\bigl(\mathrm{like}(\mathrm{chocolate})\ \vee\ \mathrm{like}(\mathrm{vanilla})\bigr).$$
The two are equivalent, because $\neg(P\vee Q) \equiv (\neg P)\&(\neg Q)$ (this is one of De Morgan's Laws: for "P or Q" to be false, you need both P to be false and Q to be false).
The second sentence is similar: "Neither e nor a is to the right of c and to the left of b".
You mention you are confused about it; I think it's just a confusion of parsing (it is a bit awkwardly constructed). What is says is "Neither e nor a satisfy xxxx". That is: "e does not satisfy xxxx, and a does not satisfy xxxx". What is this xxxx? It is the condition "is to the right of c and to the left of b".
So the sentence is the same as "neither
(Note that "e is not to the right of c and to the left of b" means that either e is not to the right of c, or e is not to the left of b, or both; same with a).
If you wanted to translate it in the same manner as the first translation above, with conjunction, you would have:
$$\Bigl(\neg\bigl(\mathrm{RightOf}(e,c)\&\mathrm{LeftOf}(e,b)\bigr) \Bigr) \& \Bigl(\neg\bigl(\mathrm{RightOf}(a,c)\&\mathrm{LeftOf}(e,b)\bigr)\Bigr).$$
But you can equally as well use the model of the second translation above, to get the equivalent statement:
$$\neg\Biggl( \bigl(\mathrm{RightOf}(e,c)\&\mathrm{LeftOf}(e,b)\bigr) \vee \bigl(\mathrm{Rightof}(a,c)\&\mathrm{LeftOf}(a,b)\bigr)\Biggr).$$
So now you see the disjunction in the second.
The reason why the first "translation" of this phrase might be better than the second is that the mix of conjunctions and disjunctions ( "(a and b) or (x and y)" ) is usually a little harder to parse than a sequence of conjunctions, even with negations ( "not(a and b) and not(x and y)"). So the latter form is slightly prefered for parsing reasons, but mathematically they are equivalent. The parsing problem does not show up in the vanilla/chocolate example, because there are no conjunctions hiding inside the clauses and complicating the parsing.
You are correct about 'not both' and 'both not'. Do you need any further clarification about what they mean?
"Either A or B" is actually quite tricky. I think it may depend on the exact context sometimes whether it means "A or B but not both" (that is, exclusive or) or just "A or B" (which includes the possibility of both A and B being true).
Have a look at this question on the English Language & Usage stackexchange.
If this is an exercise for a course, then perhaps you have been told which usage is intended?
My interpretation of the third sentence before I thought about it too much was that it meant exclusive or, but now I'm not absolutely sure.
In any case, NOT(M v R) is definitely not correct, because this says that M and R are both not true (think about a Venn diagram if it helps).
Your answer for 4. is also incorrect. It says that Messi is not in the match or Ronaldo is not in the match (including the possibility that they might both be not in the match). Therefore it allows the possibility that one of the two might be in the match, whereas "Neither Messi nor Ronaldo is in the match" means "Messi is not in the match and Ronaldo is not in the match".
Notice that 2. and 4. both mean the same thing!
Best Answer
The point of the "both" and "either" here is just to disambiguate the parentheses. If you just say "p or q and r", that's ambiguous: do you mean "(p or q) and r" or "p or (q and r)"? But if you put "both" at the start, that tells you it can't be the second option: "both p or (q and r)" doesn't make sense because you can't have "both x or y", only "both x and y".
So "both p or q and r" just means "(p or q) and r", or $(p\vee q)\wedge r$ in symbols. Similarly, "either p and q or r" just means "(p and q) or r".
For your second set of examples, you are right about the first one but the second one is wrong. "Neither p nor q" means that p and q are both false, whereas your proposed $\neg p\vee\neg q$ means only that at least one of p and q is false (since it says "p is false or q is false").