Suppose you have a lot of work to be done, and want to get it done much faster, so you hire 100 workers. If the work is 100 separate jobs that don't depend on each other, and they all take the same amount of time and can be easily parceled out to the workers, then you'll get it done about 100 times faster. This is so easy that it is called embarrassingly parallel.
And from your own Wikipedia source:
is one for which little or no effort is required to separate the problem into a number of parallel tasks. This is often the case where there exists no dependency (or communication) between those parallel tasks.
It says it right there, it requires no effort.
From what I gather, it is considered embarrassing because it is easy.
Definition of embarrass:
verb [with object]
1cause (someone) to feel awkward, self-conscious, or ashamed: she wouldn’t embarrass either of them by making a scene
(be embarrassed) be caused financial difficulties: he would be
embarrassed by estate duty
2 archaic hamper or impede (a person or action): the state of the rivers will embarrass the enemy
archaic make difficult or intricate; complicate:
I do not apprehend that this case will be embarrassed by that decision
Edit for OP
The etymology of embarrass:
1670s, "perplex, throw into doubt," from Fr. embarrasser (16c.), lit. "to block," from embarras "obstacle," from It. imbarrazzo, from imbarrare "to bar," from in- "into, upon" (see in- (2)) + V.L. *barra "bar." Meaning "hamper, hinder" is from 1680s. Meaning "make (someone) feel awkward" first recorded 1828. Original sense preserved in embarras de richesse (1751), from French (1726): the condition of having more wealth than one knows what to do with. Related: Embarrassing; embarrassingly.
I'd like to focus more on the last part:
the condition of having more wealth than one knows what do do with
When you have an embarrassingly parallel problem, you are saying you have many identical but separate subtasks to deal with
An example is a cryptographic brute force attack, in which the algorithm is to independently try billions of random inputs until one works.
this example is from your own question
For the other answer, a synonym of easy is simple.