However, what about contracts? One President, say of some extreme
political philosophy, could hire many people into the executive branch
and then give them long "employment contracts" that obligate the US
government to employ them for 30 years. When a different President
becomes elected can he then dismiss those employees and abrogate the
contracts? On one hand he should have this power under the
Constitution, but on the other he would be violating contract law. How
is this contradiction resolved legally?
The President doesn't employ anybody (well, the President could and our current President probably does, but a contact between the President and an employee in his personal capacity is beyond the scope of this question). In the cases relevant to the question, it is the United States government that is the employer. For what it is worth, the case law also holds that apart from certain independent agencies and corporations, the United States government is a unitary entity.
For example, one isn't an employee of the White House or of the Justice Department or even the judicial branch, you are an employee of the government of the United States of America, but, for example, the Postal Service is a government owned and controlled company, so that is different.
As noted by @pboss3010, the vast majority of employees are not hired by the President and are instead either under the federal civil service or by the Department of Defense, which has regulations that govern the terms of employment contracts. Others are hired by political appointees unilaterally (who may themselves have been appointed by a prior President even) and not by the President.
There are about 7000 positions for which the President or another political appointee of the President has the authority to hire someone, and those are listed in a publication called the Plum Book (after the historical cover color of this publication). Most positions have, by virtue of the legal authority creating them, either a statutorily fixed term of years (e.g. the FBI director has a 7 year term), or are "at will" positions for an indefinite term.
But, while in a contract with a private party, a contract is valid if the person signing it merely has "apparent authority" to do so, in a contract with a government, such as the United States, a contract is only valid if the person signing it on behalf of the government has actual authority to do so.
Absent statutory authority to do so, the President does not have actual authority to hire someone in a employment contact that extends beyond his term of office (there are similar constitutional cases limiting the authority of Congress to bind future Congresses absent specific constitutional authority, e.g., in the case of naval contracts).
So a contract of the type mentioned in the OP would be void or voidable by the United States government because the President did not have the actual authority to enter into a contract for that term.