Also, mapreduce is not embarrassingly parallel. Out of mapreduce, map is the only embarrassingly parallel phase. It has input parsing, shuffle, reduction phases that are not embarrassingly parallel.
We're certainly not the first to describe mapreduce as "embarrassingly parallel," but I can defend myself nonetheless:
A shuffle executes in parallel where each unit re-indexes into another unit. Reduction is parallelized over each key, and even finer granularity can be achieved by considering a tree-based approach:
http://developer.download.nvidia.com/compute/cuda/1.1-Beta/x...
In fact, I used this tree reduction approach to merge non-disjoint clusters of friend groups in my social network clustering algorithm.
Parallelizing the input parsing is problem-specific, but even that is possible in many cases.