I believe the typical Saemisch-type strategic approach of doubling the c-pawns, fighting against the weak front c-pawn and big center, was invented in the mid-19th century in England. Elijah Williams beat Staunton and others using it--though not with this exact move order.

The Nimzo move order proper was tried in 1883 by Blackburne  (his opponent played 5.Bd2, and he played ...b6 and ...d5), and then in 1914 by Alekhine (who played ...b6,...c5 and ...d5 against Rubinstein's 5.e3) and Nimzovitch (who played the typical dark-square strategy of ...c5, ...d6, and ...e5 against Janowski's 5.e3). It was not a way of avoiding a feared variation, but rather part of the general exploration, by both hypermoderns like Gruenfeld and others like Maroczy, of new ways to treat the center. Nimzovitch himself played it a lot from 1922 on, usually with ...b6 and Bb7. By 1926, even Tarrasch(!) used it to win a beautiful game against Gilg with ...b6, ...Bb7 ...Ne4, and ...f5 .

At that time the QGD Exchange variation, while not unknown, was not thought very frightening. Otherwise, Capa and Alekhine would have used the Exchange against each other at least once in their match, or else avoided 3.Nc3. The Exchange's reputation grew especially after Botvinnik-Keres, when Botvinnik produced the plan with f3 and Ne2, and again during the 1980s when Kasparov used it to defeat Anderson and others. Today I think it is not particularly feared. Of course, the Nimzo is much less constrained for both sides than the QGD Exchange--less technical, more unbalanced, and strategically richer. I think players avoid the 3.Nc3 QGD today, if they do, not so much out of fear as out of a desire for a different sort of game.

I myself play both the Nimzo and the QGD as Black, usually with the Nimzo order, but not always. By the way, if you want to know how to play against the Exchange, read Ntirlis' Classical Repertoire.