So Zeidman stood up at his first meeting and told the board, "There are no elephants on my tie. This is a totally nonpartisan position. We are here for the future of this museum, and we need to keep politics out of the museum."
A group of Democratic women on the board, including law professor and Democratic pundit Susan Estrich, encouraged others to give Zeidman, a Houston-area businessman and local Jewish communal leader, a chance.
"I think at the outset there was concern that President Bush was appointing his best Jewish friend, a major supporter and donor, rather than a 'Holocaust person,' " Estrich wrote in a recent e-mail to JTA, "but I always thought the fact that the museum was the job that Fred -- who could have had his choice of plum spots in the administration -- wanted was a clear sign of his commitment and his values."
"I think the museum today is stronger because of his leadership," she added.
While some other Bush friends who were appointed to top jobs in Washington will go down in history as mistakes, there is broad agreement that Zeidman's tenure leading the governing board of the U.S. Holocaust Memorial Museum has been a success -- and that partisan politics were never an issue with him at the helm, even as he remained a Bush buddy, served as a leader of the Republican Jewish Coalition and became an active supporter of Sen. John McCain's presidential campaign.
Current and former members of the 55-person council and others connected to the museum say Zeidman helped bring a stability and professionalism that sometimes had been lacking in previous years. They also credit him with shepherding the 15-year-old institution into its second decade by broadening its focus beyond just telling the story of the Holocaust to examining the tragedy's lessons and legacy.
That expansion in focus has led to one of the signature accomplishments of Zeidman's tenure: a higher profile and bigger budget for the museum's Committee on Conscience, which has called attention to genocide around the world, particularly in Africa.
The museum took the lead among branches of the federal government in labeling the mass killings in Darfur as genocide, teamed up with Google to use satellite technology to identify villages that were destroyed, projected images of the Darfur genocide on the walls of the museum during Thanksgiving week two years ago, began producing a regular podcast aimed at drawing attention to genocide and created a genocide prevention task force that recently filed its final report.
"There had to be a much broader emphasis on the causes of genocide and prevention of genocide," said Zeidman, 61, in a recent interview in his museum office.
While staffers and many council members favored the move, many survivors initially weren't on board.
"Their biggest concern was the museum would be universalized," said Zeidman, who now splits time between Texas and Washington and spends his days as senior director of governmental affairs for the Washington power law firm of Greenberg Traurig.
However, he added, eventually they were convinced that "the only way their legacy would be intact is if lessons of the Holocaust were transmitted to future generations."
Zeidman said that a discussion the museum held among survivors of the Holocaust and the Rwandan and Darfur genocides was "the most impactful moment" he has experienced at the museum. It was the sort of experience that validated his decision to push for the chairmanship, when as a longtime Bush friend he had plenty of options.
"I felt like I wanted a job up here that would be meaningful and I could really accomplish something," he said. "To my way of thinking, the chairman of this Holocaust museum is probably the most meaningful position for a Jew in America."
Zeidman took the helm at the council in the wake of a series of controversies that had dogged the museum's leadership. He succeeded the trouble-plagued two-year tenure of Rabbi Irving "Yitz" Greenberg, who was criticized for writing a letter on museum stationary requesting a pardon for fugitive Marc Rich and became a target of activists -- many felt unfairly -- for a speech he gave about the Israeli army's response to the second intifada.
Two years earlier in 1998, then-chair Miles Lerman's invitation to PLO chief Yasser Arafat for a tour resulted in the resignation of the museum's then-director, Walter Reich.
Zeidman said that as the first chairman to not come from the "Holocaust community," and with no direct familial connection to the Holocaust, he was able to avoid some pitfalls because he was coming in with a "clean slate."
"Those controversies were all based in the passion of those people to do what they thought was right for this museum," Zeidman said. "I could be dispassionate where they had this passion. This was their baby -- all they had lived and breathed for so many years -- and I could take a step back" and view things from a different perspective.
The ability to avoid tensions was important because "controversy is so disruptive to the day-to-day management of the museum," he said. "The main thrust is to reduce controversy, to reduce the amount of time executives have to spend in doing anything else besides running the museum."
That's why, when some survivors were upset with the museum over the speed with which it was allowing access to the newly acquired Bad Arolsen International Tracing Service archive, he invited them to Washington earlier this year for a meeting.
Zeidman viewed the acquisition of the archive as the "seminal accomplishment" of his time at the museum, and suddenly the institution was being criticized over it. So he organized the meeting with survivors to detail "what we're doing and how we're doing it."
Sam Dubbin, the lawyer for the Holocaust Survivors Foundation, said the group appreciated the opportunity Zeidman provided.
"There's no question museum leaders learned a lot from having the survivors there," he said.
Another dispute Zeidman defused came in 2006, when former New York Mayor Ed Koch called on radio talk show host Dennis Prager to resign from the council because Prager criticized Rep. Keith Ellison (D-Minn.) for using a Quran in his congressional swearing-in ceremony.
After many hours on the phone with Koch and Prager, Zeidman said he got both to realize that "the controversy had nothing to do with this museum" and that it had become "an innocent victim." The museum's executive committee sent out a statement disassociating itself from Prager's remarks and the issue was settled.
"I was very happy with how it was handled," said Koch, adding that Zeidman was adept at dealing with such disputes. "He handled all of his problems, whatever they were, in a way that we never even knew there was a problem."
As a veteran of corporate boards, Zeidman also changed the role of the council chair. Past chairs, those associated with the museum say, sometimes became too involved in the day-to-day operations of the institution.
Zeidman recalls that upon his arrival, "they were bringing me all these little bitty personnel decisions. I said what is this about?"
"You don't hire a professional and then not give her the authority to run the museum," said Zeidman, referring to museum director Sara Bloomfield, whom he praised numerous times during an hourlong interview.
Ruth Mandel, vice chair of the council from 1993 to 2005, said Zeidman trusted his staff.
"While he was certainly a presence, he knew what his role was as the chair of the governing board and what the role of staff leadership should be -- and he knew how to develop a good partnership," she said.
"He was someone who had a sense of what his role was, who didn't want to be in charge of day-to-day operations," said Deborah Lipstadt, an Emory University Holocaust scholar and former board member, who added that some of the problems in the museum's first decade were simply attributable to "growing pains."
"He was the right person for the right time," she said.
Others on the council praised Zeidman's leadership style.
"What makes him so effective is he asks for input from everybody and then together decisions are made," said Dottie Bennett, a current member of the council executive committee. "Nothing is presented to us as a fait accompli, so you really feel you are a part of the team."
Not everyone was always a fan of Zeidman's more business-minded, noncontroversial approach. One person close to the museum, who did not wish to be identified, said that controversy isn't necessarily bad -- it can also mean that the museum is "on the cutting edge."
Michael Berenbaum, a board member from 1998 to 2003, said that as a scholar and academic, he sometimes disagreed with Zeidman's outlook. For example, Zeidman thought the minutes of council meetings should only list decisions taken, while Berenbaum preferred that the document include a description of the nature of debate so that scholars could study and learn from it in the future.
Berenbaum, who also served as project director during the building of the museum and director of its research institute from 1993 to 1997, was outvoted in the council's executive committee.
"Fred was correct if you're a corporate officer and don't want to be sued," Berenbaum said. "I thought the museum is a historical institution and should not treat itself as safe."
But Berenbaum also had praise for Zeidman.
"He brought stabilization to the museum" and "essentially conflict-free stewardship," said Berenbaum, and that is "a significant achievement."
While Bush may be leaving town next month, Zeidman -- who spends a couple of weeks each month in the capital -- isn't going anywhere just yet. He was named to a second five-year term on the council last year and said he intends to stay on the board through its conclusion in 2012.
While he would be happy to remain as chairman, Zeidman said he will defer to President-elect Barack Obama's wishes.
This is one Bush appointment that even the president's most vocal opponents will miss.
"I have been a very strong critic of the Bush administration," said former council member and lawyer Menachem Rosensaft, but "one of the outstanding appointments that George W. Bush made was appointing Fred chair of the Holocaust Council."
"He has kept the museum out of politics," Rosensaft said, "and maintained it as a major American institution."