I feel like that was Roosevelt. His New Deal, his speech about our freedom from fear and want. His foreign policies.

The description of Truman as the last "everyman" president, isn't really derived from his domestic policies, but from his personal background. Truman was not a college graduate, had spent most of his young life as a bank clerk, a farmer, a store owner, a low ranking military officer, then in local political offices where he was known for being non-partisan and fair. The biggest reason he even got into politics is because to be honest...he wasn't great at anything else but being a bank clerk and army officer and needed a good paying job. He parlayed his local reputation as a good guy into winning office. His choice in words, his public persona, his willingness to 'walk among the little people' by eating at local diners, attending lodge meetings, and even after his presidency just walking by himself around the streets of New York like he wasn't anyone special. Hell, he was even on a very early episode of Candid Camera.

It seems like Truman turned it all on it's head, damaging or destroying any political will and influence we had gained with Churchill and Stalin

To describe the Allies in WWII, I heard it best put more accurately as "The Allies and the Soviets." Stalin was always adversarial, seeking leverage, and actively spying on his temporary allies. Stalin new about the Manhattan Project before Truman did. Stalin was always going to return to an adversarial position after the war, and it is best evidenced by such actions as the Berlin Blockade in 1948, active espionage and agitation in the U.S. government, and creating proxy states in Eastern Europe.

As far as Churchill. Churchill was out of office by the end of 1945, and didn't return to the office of Prime Minister until 1951.

threatening Stalin with nuclear weapons in northern Iran if he didn't withdraw within 48 hours

If you're referring to the 1946 crisis, in which the Soviet Union refused to leave Iran according to earlier agreements. The US had already left, Britain had set it's withdrawal date, but the Soviets remained. Truman, already having felt like Stalin had dealt unfairly with his former allies, now recognized that Stalin was in violation of the 1942 treaty and recognized that the Soviets expansion of forces in Iran was shaping up to be similar to what was happening in Eastern Europe. After several UN Resolutions were passed and the Soviets did not withdraw Truman threatened to use force. It was two weeks before the Soviets actually began to withdraw.

Truman pushed us into a state of perpetual war economy

Could you explain your assertion for this, since under Truman a massive demobilization took place which created what was in essence a 'hollow army'. When the U.S. deployed forces to Korea in 1950, they were horribly under supplied, because Truman was adamant about reducing defense spending. In fact, according to one memorandum, the U.S. Navy was incapable of enforcing a blockade on Korea in July 1950 due to inadequacies. In fact, the famous NSC-68, which called for a reexamination of America's foreign policy and defense posture was met with resistance from Truman who kept sending it back telling them to cut costs! Between 1945 and 1950, there was a HUGE reduction in defense spending by Truman, which only increased because of Korea. The policy paper may have encouraged it, but Korea created it, and every president after Truman expanded it.

and set us up as the world police force

Truman's foreign policy against the Soviets/Communists was one of containment. Truman kept the U.S. out of the renewed Chinese Civil War between Mao and Chiang Kai-Shek. He refused to use force to resupply Berlin in 1948. He only moved in Korea after a UN resolution was passed, and in Vietnam he provided funds and material, but did not want U.S. troops involved. Truman heavily pushed for the United Nations, and used it often to back his international policies.

As for Wallace as VP?

FDR was off of Wallace before the convention, since most of his advisor's didn't like him for being too far left and a bit of an eccentric. Truman wasn't even at the top of the list of picks to replace him initially and FDR preferred Supreme Court Justice William O. Douglas.