In acknowledging that 'Fat Albert' is a nickname adopted in the RAF for the C-130, I believe that the name may have been first used for the C-5A within USAF's Military Airlift Command. It was certainly already in being when the first aircraft arrived at Travis AFB in 1970, with HQ MAC trying hard, but fruitlessly, to stamp it out. (And I don't recall ever hearing anyone at that time use the term for a 130.)