The Social Security Act was passed in 1935, the same year that the Gallup Poll began, and the first check was issued in 1940. This is a pretty complete list of opinion questions about Social Security asked in the early years:
Dec 1937. "The present Social Security law does not cover household help, sailors, farm workers, and employees in small shops. Do you think the law should be extended to include these workers?" yes: 74% no: 26%
Dec 1937: "Do you approve of the present Social Security tax on wages?"
yes: 73% no: 27%
July 1938: "DO YOU APPROVE OF THE PRESENT SOCIAL SECURITY LAWS WHICH PROVIDE OLD AGE PENSIONS AND UNEMPLOYMENT INSURANCE?"
yes: 78% no: 18%
April 1943 (NORC): "As you may know, under the present Social Security Law, workers in certain occupations have to save money so when they are too old to work they will receive money from the government, like insurance. Do you think this is a good idea or a bad idea?"
good idea: 95% bad idea 3%
Debate over domestic issues was muted during the war, so to be fair I'll add a question from 1946. There was a sharp move to the right in that election, with Republicans winning control of both houses of Congress (one of the new members of the House was Richard Nixon):
Dec 1946 (Roper/Fortune): "Would you like to see Social Security extended so that more people will get payments under it, changed so that fewer people will get payment under it, or left about as it is now? "
more: 49% fewer: 2% same 34%
Social Security was clearly "broadly popular" long before Nixon became president. Unfortunately, it's not possible to say whether it was popular when first proposed or whether it became popular soon after it was enacted. With Medicare, there was a shift--opinion was pretty evenly divided when it was proposed but swung in favor.
[Data from the Roper Center for Public Opinion Research]