The government is bound by acquisition processes for these large contracts: they put out RFPs and companies compete for the contract. All Google has to do is not bid for the next contract.

Yes.

They could be nationalized in times of war, but that hasn't happened since WW2 I think.

The antitrust case and other regulatory arm twisting is more to worry about.

Yes they absolutely can. Providing services to the government is strictly a choice made by the business.

There is an exception that can be made by the government for wartime, but otherwise, yes.

I think it's kind of past the point of wondering what somebody can and cannot do according to the law? There used to be the constitution and stuff.

Pretty sure the 13th Amendment guarantees this, in theory. (Corporations aren't natural persons, but forcing a corporation to provide a service boils down to forcing people to provide a service.)