The numerical instability of GS is due to loss of orthogonality, not so much errors in normalization.
Householder and Givens approaches are about equal AFAIK, but the wikipedia article claims Givens is easier to parallelize. I am not sure that applies for Map-Reduce. Givens is definitely easier to apply in a sparse case since you don't have to deal with an entire (mostly zero) row or column at a time.
Golub and van Loan, p 219 (2nd edition) has a discussion that shows that the error for modified Gram-Schmidt is about k u where k is the condition number of the matrix and u is a single ULP while Householder and Givens approaches have error about the same as u. This implies that hilbert matrices might be good test cases.