The Government as employer bears a special burden. Absent contrary legislation, a private employer may regulate the workplace environment, and hire, fire, and promote as it pleases. The Government enjoys no such freedom. As the Supreme Court has said, “the state and federal governments, even in the exercise of their internal operations, do not constitutionally have the complete freedom of action enjoyed by a private employer.” Cafeteria & Rest. Workers Union, Local 473 v. McElroy, 367 U.S. 886, 897-98, 81 S.Ct. 1743, 6 L.Ed.2d 1230 (1961). The Government as employer may not discriminate arbitrarily, regardless of the statutory regime, see Rutan v. Republican Party of Ill, 497 U.S. 62, 98, 110 S.Ct. 2729, 111 L.Ed.2d 52 (1990), and conspicuously unlike a private employer, it must respect its employees’ First Amendment rights to free speech, see City of San Diego v. Roe, 543 U.S. 77, 80, 125 S.Ct. 521, 160 L.Ed.2d 410 (2004).
At the same time, the Supreme Court has recognized, in a variety of doctrinal contexts, that “the status of the Government as a ... market participant must be sharply distinguished from the status of the Government as regulator or administrator.” Dir., Office of Workers’ Comp. Programs v. Newport News Shipbuilding & Dry Dock Co., 514 U.S. 122, 128, 115 S.Ct. 1278, 131 L.Ed.2d 160 (1995). As a result, even the Government as an employer, and hence as a consumer of labor, must retain some freedom to dismiss employees who do not meet the reasonable requirements of their jobs. In the ease before us, we must reconcile a Government employee’s right to engage in protected speech with the right of a Government employer “to protect its own legitimate interests in performing its mission.” Roe, 543 U.S. at 82,125 S.Ct. 521.
The plaintiffs — former New York Police Department (“NYPD”) officer Joseph Lo-curto and former New York Fire Department (“FDNY”) firefighters Jonathan Walters and Robert Steiner — brought suit against the defendants — former New York City Mayor Rudolph Giuliani, former NYPD Commissioner Howard Safir, former FDNY Commissioner Thomas Yon Essen, and the City of New York — claiming that they were illegally fired from their positions in the NYPD and the FDNY in retaliation for their participation in a Labor Day parade, on a float that featured mocking stereotypes of African-Americans. The district court entered judgment for the plaintiffs, holding that they were discharged, not on any legitimate grounds, such as the disruption or threat of disruption that their actions had caused to the operations of the police and fire departments, but in retaliation for the content of their speech, and hence in violation of the First and Fourteenth Amendments. Because we conclude that the defendants fired the plaintiffs out of a reasonable concern for disruption, and that this concern outweighed the plaintiffs’ individual expressive interests, we reverse the district court, and remand the case to that court with instructions to enter judgment for the defendants.
Background
Each of the three plaintiffs is a white resident of Broad Channel, a small, predominantly white, island community in southeast Queens. Locurto, a Broad Channel native, was an NYPD officer from 1994 until his termination in October 1998. During that time, he was assigned to the racially-mixed 104th precinct in Queens and received consistently positive reviews from his supervisors there. Steiner, who *164has lived in Broad Channel since 1996, was an FDNY firefighter from 1996 until October 1998. At the time of his firing, Steiner was assigned to Ladder 17 in the South Bronx, a 98 percent minority community. There had never been any reported problems between Steiner and his colleagues or the public. Walters is a lifelong Broad Channel resident who joined the FDNY in 1990. For the three years leading up to his discharge in October 1998, he worked at Engine Company 231 in Brownsville, a predominantly African-American and Hispanic neighborhood in Brooklyn. All of Walters’s performance evaluations during his FDNY tenure showed a rating of “satisfactory” or higher, and he had no reported difficulty with any of his fellow firefighters, four of whom were African-American.
The Float
Each year, Broad Channel plays host to a loosely organized Labor Day parade. The parade features, among other things, floats with varying themes and of varying degrees of sophistication. Local politicians award prizes to floats designated, for example, “prettiest,” “most original,” and “funniest.” In each of the nine years leading up to 1998, the prize for funniest float was awarded to a particular group of individuals who entered floats that often, but not always, featured racial, ethnic, or other stereotypes, and that played off themes from popular culture. In 1994, for example, this group entered a float entitled “Hasidic Park,” a play on the film Jurassic Park, that featured stereotypes of Hasidic Jews living in prehistoric times. The group’s 1996 float, called “Gooks of Hazard,” depicted Asian stereotypes. Another year, the float styled itself “Happy Gays” and made fun of gay men. Steiner and Walters participated in each of these floats, and Locurto in the 1996 and 1997 floats. There is no evidence that any of the previous floats generated any substantial contemporaneous controversy or public attention.
For the September 7, 1998 Labor Day parade, the group, which included the plaintiffs, decided to enter a float called “Black to the Future — Broad Channel 2098.” The conceit, a play on the 1985 time-travel film Back to the Future, was to depict how Broad Channel would look in 2098 when, presumably, the community would be more integrated than it was in 1998. Each of the float participants, including the plaintiffs, covered their faces in black lipstick, donned Afro wigs, and accompanied the float along the procession in attire ranging from overalls with no T-shirt underneath, to cut-off jeans and ratty T-shirts, to athletic pants and sweatshirts. The float itself featured two buckets of Kentucky Fried Chicken on the hood of a flatbed truck. One of the participants (not a plaintiff in this case) ate a watermelon and at one point threw the remains into the crowd. The float participants engaged in various chants, including, “No Justice, No Peace,” “This isn’t Johannesburg,” and “We didn’t land on Broad Channel, Broad Channel landed on us.” 1 Plaintiffs Steiner and Walters yelled to the crowd, “Crackers, we’re moving in,” and Walters simulated “break dancing” alongside the float.
*165Near the end of the procession, and apparently without the others’ knowledge, Walters held onto the truck’s tailgate, pretending to be dragged by the truck, and yelled, “Look what they did to our brother in Texas, we would not allow them here .... ” The scene was intended to invoke and parodieally recreate the dragging death of James Byrd, Jr., an African-American man who had been murdered months earlier outside of Jasper, Texas after being chained to the back of a moving pickup truck by three white men.
The float never reached the viewing stand to be sized up for the annual funniest float prize because a thunderstorm ended the parade early.
Reaction to the Float
The next evening, a local news broadcast aired amateur video footage of the float in a piece entitled “Racist Float.” Extensive press coverage followed immediately, with the New York Times reporting three days later on the front of its Metro section that, according to “city officials,” New York City police officers and firefighters had taken part in the float. See David W. Chen, Officers and Firemen Wore Black-face on Float, Officials Say, N.Y. Times, Sept. 11, 1998, at Bl. The paper quoted Mayor Giuliani as saying, in a statement, “ ‘I’ve spoken to Commissioners Safir and Von Essen and we all agree that any police officer, firefighter or other city employee involved in this disgusting display of racism should be removed from positions of responsibility immediately.... They will be fired.’” Id.
On the afternoon of September 11, 1998, the day the Times story ran, Locurto learned that the NYPD wanted to speak to him about his participation in the float. He contacted the Department’s Legal Bureau through an attorney and said that he had, in fact, participated; shortly thereafter, with no further inquiry into the nature of Loeurto’s involvement, the NYPD sus--pended him without pay. Also on September 11, Steiner and Walters appeared voluntarily before Von Essen to report their participation in the float. They, too, were subsequently suspended without pay. Von Essen told Steiner and Walters that, were it up to him, he would not fire them, but that his hands were tied.
More media attention followed. On Saturday, September 12, Rev. Al Sharpton led a group of demonstrators through the streets of Broad Channel. In a story appearing the same day, Giuliani was quoted as saying of the plaintiffs, “They’re technically suspended, but they’re never getting back into the Police Department or the Fire Department unless the Supreme Court of the United States ordered us to take them back.” Gene Mustain, Float Firefighters Shelved, Daily News (N.Y.), Sept. 12, 1998, at 7. Giuliani was- also quoted as saying, “Police officers [and] firefighters carry a very heavy responsibility ... to treat people fairly. That responsibility cannot be placed in doubt.” Id. (alterations in original). A New York Times story that ran the next day further quoted Giuliani as saying, “I’m not going to take the responsibility of keeping [Locurto] on the police force and then three years from now he hurts somebody and somebody wants to know why he wasn’t removed.” Kit R. Roane, “ ‘Suspended Police Officer Apologizes, Calling Float ‘a Big Mistake,’ ” N.Y. Times, Sept. 13, 1998, at 51.
The plaintiffs’ float and Giuliani’s comments came in the immediate wake of a controversy over the NYPD’s handling of the September 5, 1998 “Million Youth March.” Giuliani had publicly denounced the march organizer, calling former Nation of Islam official Khalid Abdul Muhammad a “hatemonger” over comments, which Giuliani regarded as offensive, that Muhammad had made about Jews and Catholics. *166The City initially denied a permit to march organizers, but a permit issued after the organizers obtained a federal injunction. See Million Youth March, Inc. v. Safir, 18 F.Supp.2d 334 (S.D.N.Y.1998). Some of Giuliani’s critics later objected that the NYPD used excessive force to break up the march shortly after it ended.
Locurto’s NYPD Hearing
The NYPD filed two charges against Locurto on September 14, 1998:(1) “conduct prejudicial to the good order, efficiency and discipline of the Department” by participating in a Labor Day parade float “which depicted African-Americans in a demeaning and offensive manner” (“Specification No. 1”), and (2) “knowingly associating] with person(s) or organization(s) advocating hatred, or oppression of, or prejudice toward a racial or religious group” (“Specification No. 2”). Under NYPD administrative procedures, such charges must be adjudicated at a hearing before the Deputy Commissioner of Trials. The Deputy Commissioner then issues a Report and Recommendation to -the Police Commissioner, who makes a final determination.
Locurto’s hearing was held October 5, 1998, before Deputy Commissioner of Trials Rae Downes Koshetz. Locurto and the Department agreed to two stipulations of fact to be entered at the hearing: (1) that the NYPD had not terminated any officer solely for having engaged in racially offensive speech or expression since January 1991, and (2) that the NYPD had no knowledge of any case in which charges were filed against an officer for alleged violation of Specification No. 1 since January 1, 1980.
Each side presented two witnesses. The Department offered James Trudden, an NYPD detective and chief of the Broad Channel Volunteer Fire Department, and James O’Keefe, the NYPD’s Director of Training. Trudden testified to the particulars of the Labor Day Parade, in which the Volunteer Fire Department also regularly participated. Trudden also said that when he saw the news report the day after the parade, he recognized the plaintiffs personally from having lived with them in Broad Channel. O’Keefe testified to the professionalism training Locurto had received. O’Keefe noted that the training program emphasized the lack of any distinction between on-duty and off-duty behavior.
Locurto appeared on his own behalf. He discussed his involvement in past years’ floats and his participation in the 1998 float. He said he had not used any racial slurs or thrown any objects, and that he had been unaware, when the procession began, that Walters would re-enact the murder of James Byrd, Jr. On cross-examination, Locurto said that his only purpose in entering the float was to win the prize for funniest float, and that he did not intend for the float to represent political commentary.
Locurto’s second witness was Rev. Sharpton, who testified to the motivation behind the protest he organized. The float, Sharpton said, “was indicative of a systemic problem where people high in the Police Department and Fire Department apparently allow an annual event going on parodying people.” Locurto Hearing Transcript at 239. Sharpton said that he and his followers “felt the Mayor who was in political trouble because the nation watched the films of the Million Youth March and was trying to scapegoat the police officer and firemen to try to be a balancing, [sic]” Id.
Locurto wanted to depose Giuliani and Safir and question them on their motivations for suspending him, but Deputy *167Commissioner Koshetz denied him leave to depose them.
After listening to testimony and closing arguments, Deputy Commissioner Koshetz recommended that Locurto be found guilty of Specification No. 1, but recommended that Specification No. 2 be dismissed. She concluded, based on Loeurto’s testimony, that the float did not express an opinion on “a matter of public concern,” but rather “was designed to mimic and mock a racial group for the amusement of the participants and spectators.” In re Charges and Specifications against Police Officer Joseph Locurto, Case No. 73662/98, at 11 (N.Y.P.D Oct. 9, 1998). Moreover, Deputy Commissioner Koshetz found, given the negative media coverage and public response that followed the parade, the NYPD had made “an ample showing of both actual and potential disruption of the Department’s working relationships among members of its own work force as well as its ability to function effectively in the multi-cultural environment of our city.” Id. at 14. Deputy Commissioner Koshetz concluded that, “[i]n light of the egregiousness of [Locurto’s] misconduct and the overwhelmingly negative notoriety this has wrought upon [the] Department and upon thousands of his colleagues who have never thought or acted out in this fashion,” the appropriate discipline was to dismiss Locurto from the police force. Id. at 20-21.
Effective October 10, 1998, Safir adopted the recommendation and ended Locurto’s NYPD employment.
Steiner’s and Walters’s FDNY Hearing
The same month, an administrative law judge (“ALJ”), Rosemarie Maldonado, held a hearing on charges filed against Steiner and Walters by the FDNY. Each was accused of violating three FDNY regulations: (1) “engaging in an activity instrumental in arousing racial hatred” (“Charge No. 1”); (2) “conduct unbecoming,” for “taking part in ... a float which depicted African-Americans in a humiliating, callous, and demeaning manner” and for taking part in a reenactment of the James Byrd, Jr. murder (“Charge No. 2”); and (3) violating their oaths of office (“Charge No. 3”).
The FDNY called as witnesses, among others, William Feehan, the Department’s first deputy commissioner, Steven DeRosa, its chief of training, and Trudden. Feehan opined as to how the public reaction to the floats might have a negative impact on minority recruiting, community relations, and Department morale. Trudden discussed the impact of the float on the Broad Channel Volunteer Fire Department which, after the 1998 parade, began to receive hostile phone calls, experienced rock throwing, and was labeled racist by members of the media. He also suggested that the incident had caused the City to rescind a land sale to the Volunteer Fire Department.
Steiner and Walters offered their own testimony as well as that of seven firefighters — two of whom were African-American — with whom they had worked. All seven firefighters, four of whom had worked with Steiner and three of whom had worked with Walters, testified that they had never witnessed any racist conduct by either Steiner or Walters, and all said they would welcome the chance to work with Steiner or Walters again were they to return to the Department. Steiner testified that the purpose of the float was not to be racist, but “to mimic the community’s image of racism and what they thought of a stereotype and to poke fun at them.” Steiner and Walters Hearing Transcript at 253. Walters said that he had mocked the dragging death of James Byrd, Jr. in order to “portray stereotypes of the community facing racial integration, *168a somewhat closed community and to say that we wouldn’t allow this to happen in Broad Channel.” Id. at 304.
Steiner and Walters sought leave to call Von Essen to testify about a conversation in which he allegedly said that Giuliani ordered him to fire them, but ALJ Maldonado refused to allow the testimony on the ground that it would be only “marginally ... relevant” and could be obtained in other ways. Id. at 164.
The ALJ recommended that Steiner and Walters be found guilty of Charge No. 2 (“conduct unbecoming”) and Charge No. 3 (violating their oaths of office), but that Charge No. 1 (“arousing racial hatred”) be dismissed. Unlike the NYPD hearing officer, ALJ Maldonado found that Steiner and Walters “intended to communicate a message on a mater of public concern[;]” to wit, “[t]hey were making a social statement about the future residents of their community.” Fire Dep’t v. Steiner, Nos. 559 & 560/99, at 12-13 (City of New York Office of Admin. Trials & Hearings Oct. 16, 1998). She found disingenuous, however, Steiner’s and Walters’s avowals that the float was intended “to promote an integrationist message,” id. at 13, finding instead that “[t]here is no credible evidence that the float’s message was anything but racist,” id. at 16. The ALJ then concluded that Steiner and Walters were fired based on reasonable concerns over the negative impact their speech might have on the perception of the FDNY within minority communities and on minority recruitment of firefighters. Id. at 21-25.
As to penalty, the ALJ recommended that Steiner and Walters be fired.2 Id. at 30. Von Essen adopted the ALJ’s recommendation and discharged Steiner and Walters on October 26,1998.
District Court Opinion
The plaintiffs filed their complaints individually in September 1998, and the three cases were later consolidated. See Locurto v. Safir, 264 F.3d 154, 161 (2d Cir.2001) (Locurto I). The complaints, filed pursuant to 42 U.S.C. § 1983, alleged that the plaintiffs had been suspended in retaliation for their exercise of First Amendment rights and that they had been deprived of constitutionally protected employment interests without due process of law in violation of the Fourteenth Amendment. See id. The complaints were subsequently amended to include pendent state law claims. Id.
Prior to discovery, both sides moved for summary judgment. The plaintiffs contended that the evidence of disruption of NYPD and FDNY operations was insufficient and that Giuliani had ordered the plaintiffs’ dismissals before any administrative hearings were held, thereby indicating that the dismissals were impermis-sibly retaliatory. See id. The defendants argued for summary judgment on the grounds that (1) the plaintiffs’ federal claims were collaterally estopped by the administrative determinations; (2) even if not estopped, the plaintiffs had failed to state valid First and Fourteenth Amendment claims; and (3) the individual defendants were entitled to qualified immunity. See id.
The district court denied both motions without prejudice. Locurto v. Giuliani, 95 F.Supp.2d 161, 168 (S.D.N.Y.2000). Judge Sprizzo ruled that there were factual disputes as to whether the plaintiffs had received a full and fair opportunity to litigate *169their First Amendment claims at their disciplinary hearings, and so the extent to which the findings at those hearings could be given preclusive effect was not clear on the pleadings. See id. at 167-68. Moreover, the district court held that whether the defendants were entitled to qualified immunity could not be resolved at the summary judgment stage because it could not yet be determined whether their actions in terminating the plaintiffs were “objectively reasonable.” See id. at 168 (citing Dangler v. New York City Off Track Betting Corp., 193 F.3d 130, 140-41 (2d Cir.1999)).
The defendants brought an interlocutory appeal of the district court’s refusal to grant summary judgment on the issue of qualified immunity. See Locurto I, 264 F.3d at 162. A panel of this Court held that we lacked jurisdiction over the qualified immunity appeal as it related to the plaintiffs’ First Amendment claims because the appeal turned on factual issues with respect to the defendants’ motives, on which the district court had to reach a final decision in the first instance for appellate jurisdiction to lie. See id. at 170. But, at the same time, we dismissed the plaintiffs’ due process claim in its entirety, rejecting the argument that the plaintiffs were owed an administrative hearing before a neutral decisionmaker, in light of the availability, under New York law, of appellate review through a neutral Article 78 proceeding. See id. at 174-75.
Judge Sprizzo subsequently conducted a three-day bench trial. The court heard testimony from each of the six individual parties, as well as from Lynn Tierney, the former FDNY Deputy Commissioner of Internal Affairs, and Sheldon Wright, the former FDNY Director of Employment Initiatives. The plaintiffs argued that their participation in the float was humorous commentary on a matter of public concern, namely the prospective integration of a predominantly white community, and was therefore fully protected speech under the First Amendment. The defendants argued that (a) both the factual findings and the legal conclusions of the administrative hearings collaterally es-topped the plaintiffs’ First Amendment claims; (b) the plaintiffs’ speech was not on a matter of public concern and therefore was not protected under the First Amendment from adverse employment action; and (c) even if the plaintiffs’ speech was protected, the defendants’ actions were legally justified by a concern over the potential disruption that the plaintiffs’ speech might cause to the effective operations of the NYPD and the FDNY.
In a written opinion dated June 23, 2003, the district court ruled in the plaintiffs’ favor. Locurto v. Giuliani, 269 F.Supp.2d 368 (S.D.N.Y.2003). The court found that the administrative determinations were not entitled to collateral estoppel effect because the plaintiffs, having been denied discovery into the defendants’ motives, did not receive a full and fair opportunity to litigate the crucial issue of the motivation behind their dismissals. See id. at 382. As to the First Amendment claims, the district court held that the plaintiffs’ participation in the float was protected speech on a matter of public concern, and that the defendants had improperly fired the plaintiffs in retaliation for the content of that speech rather than over any reasonable concern for potential disruption. See id. at 388, 395. Because, the district court held, the defendants acted out of an improper motive, they were not entitled to qualified immunity under our holding in Locurto I that “it can never be objectively reasonable for a government official to act with the intent that is prohibited by law.” Lo-curto I, 264 F.3d at 169 (citing Crawford-El v. Britton, 523 U.S. 574, 589, 118 S.Ct. *1701584, 140 L.Ed.2d 759 (1998)), cited in Locurto, 269 F.Supp.2d at 402 n. 23.
The district court issued final judgment in November 2004, and ordered all three plaintiffs reinstated to their former positions. Judge Sprizzo also awarded compensation for lost wages and benefits. The defendants timely filed notice of appeal on December 10, 2004.
Discussion
Before reaching the difficult legal questions this case poses, we must establish the factual record. The administrative hearings made certain findings to which the defendants contend we are required to defer. Specifically, the NYPD hearing found that Locurto participated in the float to poke fun and elicit laughter rather than for any political reason, whereas ALJ Maldonado concluded that Steiner and Walters were making a social statement through their actions. ALJ Maldonado also declared that the motivating factor behind the suspensions was the defendants’ belief that the plaintiffs’ actions “had a negative impact on their operations,” and that this motivation was not in dispute.
Subsequently, the district court made a number of significant determinations that it characterized as “factual findings.” The court found that the plaintiffs’ float had two goals: (1) “to comment on the future racial integration of Broad Channel,” and (2) to “win the prize for funniest float.” Locurto, 269 F.Supp.2d at 385. As to the motivation behind the dismissals, the district court found that the defendants were not motivated by any concern for disruption of their operations but instead “terminated plaintiffs in response to the content of their speech and for reasons of public perception and the political impact expected to flow therefrom.” Id. at 395. Moreover, the court found “as a matter of fact” that, even if the defendants fired the plaintiffs out of a concern for potential disruption, that concern was unreasonable. Id. at 395-96.
If the district court correctly refused to give collateral estoppel effect to the administrative factfinding, our review of the court’s factual findings is limited to correcting clear errors. Skoros v. City of New York, 437 F.3d 1, 12 (2d Cir.2006). But if collateral estoppel was appropriate, we would be required to accommodate our legal conclusions to the factual record established at. the administrative hearing. See generally Burkybile v. Bd. of Educ., 411 F.3d 306, 312 (2d Cir.2005). Accordingly, before proceeding to the merits of the defendants’ appeal, we must first address the preclusive effect, if any, of the findings of the administrative hearings. If collateral estoppel does not attach to those findings, we may then review the district court’s factual and legal findings to determine if the firings of the plaintiffs by the defendants were consistent with the City’s obligations under the First and Fourteenth Amendments.
I.
The Supreme Court has held that, as a matter of federal common law issue preclusion, “when a state agency acting in a judicial capacity ... resolves disputed issues of fact properly before it which the parties have had an adequate opportunity to litigate, federal courts must give the agency’s factfinding the same preclusive effect to which it would be entitled in the State’s courts.” Univ. of Tennessee v. Elliott, 478 U.S. 788, 799, 106 S.Ct. 3220, 92 L.Ed.2d 635 (1986) (internal quotation marks and citations omitted; alterations in original). The state courts of New York “give quasi-judicial administrative fact-finding preclusive effect where there has been a full and fair opportunity to litigate.” Burkybile, 411- F.3d at 310. In addition, *171for collateral estoppel to give preclusive effect to administrative agency findings, “the issue sought to be precluded [must be] identical to a material issue necessarily decided by the administrative agency in a prior proceeding.” Jeffreys v. Griffin, 1 N.Y.3d 34, 769 N.Y.S.2d 184, 801 N.E.2d 404, 407 (N.Y.2003).
The district court held that the plaintiffs did not receive a full and fair opportunity to litigate their First Amendment retaliation claims because they were denied adequate discovery into the defendants’ motivations for firing them. Locurto, 269 F.Supp.2d at 382. We agree. Deputy Commissioner Koshetz did not permit Locurto to depose Giuliani and Safir, and ALJ Maldonado thought the testimony of Von Essen would be only minimally probative. As Judge Sprizzo noted, however, “far from being ‘marginal,’ such discovery and/or testimony is relevant and necessary to plaintiffs’ case.” Id. An opportunity to litigate is neither full nor fair when a litigant is denied discovery, available in the ordinary course, into matters going to the heart of his claim. Cf. United States v. U.S. Currency in the Amount of $119,984.00, 304 F.3d 165, 177-78 (2d Cir.2002) (refusing, in a civil forfeiture action, to give collateral estoppel effect to findings from a criminal case because, owing to discovery limitations in criminal trials, “the Government ... would have been precluded from obtaining probative testimonial and documentary evidence from [the claimant]”). Where, as here, a Government employee claims to have been fired for an unconstitutional reason, discovery into the reason he was fired is, to say the least, relevant.3
We note, moreover, that a § 1983 plaintiff is not bound by the findings of an administrative hearing if he is “deprived of the opportunity to litigate his claim fully and fairly before a neutral arbitrator.” Colon v. Coughlin, 58 F.3d 865, 871 (2d Cir.1995) (emphasis added). Although no allegation has been made that either of the hearing officers was biased, it is undisputed that the decisionmakers were not the hearing officers, but rather Von Essen and Safir. See 3 Rules of the City of New York (“RCNY”) § 2-01(b); 38 RCNY § 15-08(a). The district court made a factual finding that “as of September 10, 1998, if the facts surrounding the Labor Day float were as initially assumed to be, the Mayor and Commissioners had decided that plaintiffs would be terminated.” Locurto, 269 F.Supp.2d at 390-91. If this finding was not clearly erroneous, then the ultimate decisionmakers in each of the two hearings made a determination as to the outcome of the hearings in advance, and therefore were not neutral arbitrators. As we discuss infra, the district court’s finding as to the timing of the decision to terminate the plaintiffs was not clearly erroneous. As such, the plaintiffs did not receive hearings before neutral arbitrators, and collateral estoppel does not attach to the findings of those hearings.4
*172II.
The Supreme Court’s First Amendment employment retaliation jurisprudence was not made for the situation before us. The seminal case, Pickering v. Bd. of Educ., 391 U.S. 563, 88 S.Ct. 1731, 20 L.Ed.2d 811 (1968), involved the First Amendment claims of a public school teacher who was dismissed by the Board of Education of Will County, Illinois, after a letter she wrote criticizing the Board’s funding choices and purported lack of transparency was published in a local newspaper. Another leading Supreme Court case, Connick v. Myers, 461 U.S. 138, 103 S.Ct. 1684, 75 L.Ed.2d 708 (1983), concerned an assistant district attorney who was fired for distributing a workplace survey that questioned office policies. More recently, Waters v. Churchill, 511 U.S. 661, 114 S.Ct. 1878, 128 L.Ed.2d 686 (1994) (plurality opinion), involved a nurse who was dismissed for complaining about her supervisor. Each of these Supreme Court cases represents a version of the paradigm First Amendment retaliation case, in which a public employee suffers adverse employment action for criticizing her employer.5
The two-step inquiry that has emerged from these cases — often called the “Pickering test” — asks first whether the employee spoke “as a citizen upon matters of public concern,” as opposed to “as an employee upon matters only of personal interest.” Connick, 461 U.S. at 147, 103 S.Ct. 1684. If the speech was on matters of purely personal concern, “the government is granted wide latitude to deal with the employee without any special burden of justification.” Melzer v. Bd. of Educ., 336 F.3d 185, 193 (2d Cir.2003); see United States v. Nat’l Treasury Employees Union, 513 U.S. 454, 466, 115 S.Ct. 1003, 130 L.Ed.2d 964 (1995) (Treasury Union). If, on the other hand, the employee spoke on a matter of public concern, a court must balance “the employee’s interest in expressing herself’ against “any injury the speech could cause to ‘the interest of the State, as an employer, in promoting the efficiency of the public services it performs through its employees.’ ” Waters, 511 U.S. at 668, 114 S.Ct. 1878 (quoting Connick, 461 U.S. at 142, 103 S.Ct. 1684).
Once an employee demonstrates that her speech was the motivating factor behind an adverse employment action, the burden shifts to the Government “to make a substantial showing of likely interference.” Jeffries v. Harleston, 52 F.3d 9, 13 (2d Cir.1995) (Jeffries II). The adverse employment action will only be upheld if: “(1) the employer’s prediction of disruption is reasonable; (2) the potential disruptiveness is enough to outweigh the value of the speech; and (3) the employer *173took action against the employee based on this disruption and not in retaliation for the speech.” Id,.; see Melzer, 336 F.3d at 193.
These guidelines are, however, just that. In practice, because First Amendment retaliation doctrine must reconcile our dual traditions of at-will employment and of robust license to speak freely without Government sanction, neat doctrinal boxes are of unusually limited usefulness. A single, mechanical test will not do for a salmagundi of challenges, involving both on- and off-duty speech, job-related and not, spoken in protest, for laughs, or, as often, just because. See McEvoy v. Spencer, 124 F.3d 92, 98 (2d Cir.1997) (“Because of the ‘infinite variety of factual circumstances in which such conflicts might arise,’ the Court has not announced a general standard in this area, but has instead relied upon ‘an identification and weighing of competing interests on a case-by-case basis.’ ” (quoting James Kimmell, Jr., Note, Politics and the Nom-Civil Service Public Employee: A Categorical Approach to First Amendment Protection, 85 Colum. L.Rev. 558, 560 (1985))). And “[although such particularized balancing is difficult, the courts must reach the most appropriate possible balance of the competing interests.” Connick, 461 U.S. at 150, 103 S.Ct. 1684. Our overriding concern is that the Government not be permitted to “condition public employment on a basis that infringes the employee’s constitutionally protected interest in freedom of expression.” Id. at 142, 103 S.Ct. 1684. With these principles in mind, we turn to the application of the Pickering test to the present case.
A.
Under our cases, the first step in the Pickering inquiry is to determine whether an employee is speaking on a matter of public concern. The question of whether a public employee’s First Amendment activity relates to a matter of public concern “is ordinarily a question of law decided on the whole record by taking into account the content, form, and context of a given statement.” Melzer, 336 F.3d at 196. Thus, in the Supreme Court case of Rankin v. McPherson, 483 U.S. 378, 107 S.Ct. 2891, 97 L.Ed.2d 315 (1987), a data entry employee in a county constable’s office who said of an attempt on President Reagan’s life, “[I]f they go for him again, I hope they get him,” was speaking on a matter of public concern because her comments were “made in the course of a conversation addressing the policies of the President’s administration.” Id. at 381, 386, 107 S.Ct. 2891. The Court made clear that “[t]he inappropriate or controversial character of a statement is irrelevant to the question [of] whether it deals with a matter of public concern.” Id. at 387, 107 S.Ct. 2891.
More recently, a panel of our Court held that an active member of the North American Man/Boy Love Association (“NAM-BLA”) and the editor of the NAMBLA bulletin, who was fired as a high school teacher after his association with the organization was revealed, was likely engaged in First Amendment activity on a matter of public concern. Melzer, 336 F.3d at 196. We said that “[a]dvocacy for a change in public perception and law, a fundamental component of democracy, is certainly a matter of public concern, regardless of the underlying subject matter.” Id.; cf. Cobb v. Pozzi, 363 F.3d 89, 102 (2d Cir.2003) (holding that the public concern test applies to freedom of association claims). It is not sufficient, on the other hand, that speech be directed at the public in order to pass the public concern test. Thus, in City of San Diego v. Roe, the Supreme Court held that a San Diego *174police officer who auctioned, on eBay, videotapes of himself stripping off a generic police uniform and masturbating was not speaking on a matter of public concern. “[Pjublic concern,” the Court said, “is something that is a subject of legitimate news interest; that is, a subject of general interest and of value and concern to the public at the time of publication.” Roe, 543 U.S. at 83-84, 125 S.Ct. 521.
Some courts, including both our Court and the Supreme Court, have questioned the extent to which the public concern test applies to off-duty speech on topics unrelated to employment. The Supreme Court noted in Roe that, under its previous decision in Treasury Union, “when government employees speak or write on their own time on topics unrelated to their employment, the speech can have First Amendment protection, absent some governmental justification ‘far stronger than mere speculation’ in regulating it.” Roe, 543 U.S. at 80, 125 S.Ct. 521 (quoting Treasury Union, 513 U.S. at 475, 115 S.Ct. 1003). In Treasury Union, in which the Court struck down a ban on honoraria for speeches and articles by Government employees, the Court held that the Government could not justify a ban on speech outside of the workplace and unrelated to Government employment on grounds of workplace disruption, and that the ban was an overly broad prophylactic against abuse. Treasury Union, 513 U.S. at 472-74, 115 S.Ct. 1003. Roe distinguished Treasury Union on the grounds that the police officer in Roe, who identified himself as employed in law enforcement on the auction site, “took deliberate steps to link his videos and other wares to his police work, all in a way injurious to his employer.” Roe, 543 U.S. at 81, 125 S.Ct. 521. In this sense, Roe’s commercial activities were, in effect, related to his employment and so could not be evaluated under the Treasury Union framework. See id.
The Roe Court’s treatment of off-duty speech that is “detrimental to the mission and functions of the employer,” id. at 84, 125 S.Ct. 521, as “outside the protection afforded in [Treasury Union]," id. at 82, 125 S.Ct. 521, underscores the fact that the public concern test does not apply neatly as a threshold test for expression unrelated to Government employment. See Treasury Union, 513 U.S. at 480, 115 S.Ct. 1003 (O’Connor, J., concurring in the judgment in part and dissenting in part) (“In contrast to some of our prior decisions, this case presents no threshold question whether the speech is of public, or merely private, concern. Respondents challenge the ban as it applies to off-hour speech bearing no nexus to Government employment-speech ____”). The public concern inquiry, developed within the context of on-the-job expressive activity, was intended to provide heightened protection to workplace speech that was close to the First Amendment’s core, that is, speech that “constituted the ‘essence of self-government.’ ” Cobb, 363 F.3d at 104 (quoting Connick, 461 U.S. at 145, 103 S.Ct. 1684). As the Treasury Union Court recognized, however, a negative answer to the public concern question was not meant to license wholesale Government disregard of employee speech rights, especially outside of the workplace. See, e.g., Berger v. Battaglia, 779 F.2d 992, 998 (4th Cir.1985) (“Pickering, its antecedents, and its progeny' — particularly Connick — make it plain that the ‘public concern’ or ‘community interest’ inquiry is better designed — and more concerned — to identify a narrow spectrum of employee speech that is not entitled even to qualified protection than it is to set outer limits on all that is.”). Indeed, mechanically applying a categorical public concern test to off-duty speech unrelated to Government employment would lead to the somewhat anomalous *175result that the Government would have far less latitude to dismiss an employee for a 'public display of racism involving public concerns than it has for, say, speech that was uttered in the privacy of the employee’s bedroom but was not on a matter of public concern. See Pengtian Ma, Public Employee Speech and Public Concern: A Critique of the U.S. Supreme Court’s Threshold Approach to Public Employee Speech Cases, 30 J. Marshall L.Rev. 121, 143 n. 140 (1996) (“It is no business of the public employer’s as to what an employee chooses to wear at an off-duty party if its interest in office operation is not in any way jeopardized. In such a situation, there is ever more need for balancing the interest of the government against that of the employee.”).
It is more sensible, instead, to treat off-duty, non-work-related speech as presumptively entitled to First Amendment protection regardless of whether, as a threshold matter, it may be characterized as speech on a matter of public concern. As our Court has recognized implicitly, the closeness of a Government employee’s off-duty, non-work-related speech to the heart of the First Amendment then becomes relevant as part of the Pickering balancing test, to be weighed against the Government’s interest only after the Government meets its burden of identifying a reasonable potential for disruption. See generally Melzer, 336 F.3d at 194 (“Attenuation of time, place, or content of speech from the workplace is ultimately accounted for in the balancing part of the process, but those factors will not absolutely preclude government regulation.”); Jeffries II, 52 F.3d at 13 (“[T]he closer the employee’s speech reflects on matters of public concern, the greater must be the employer’s showing that the speech is likely to be disruptive before it may be punished.”). But see Piscottano v. Murphy, No. 3:04cv682, 2005 WL 1424394, at *6, 2005 U.S. Dist. LEXIS 17140, at *17 (D. Conn. June 9, 2005) (“Nothing in either Roe or [Treasury Union ] suggests that the Supreme Court in those cases had decided to categorically exempt ‘off-duty’ public employee expression from the public concern requirement of Connick/Pickering.”).
But we need not today decide and hence do not resolve whether it was necessary for the plaintiffs to satisfy the public concern test as a threshold matter. This is because, given our resolution of the Pickering balancing test, infra, we can assume arguendo that the plaintiffs’ speech in this case did in fact relate to a matter of public concern. See Melzer, 336 F.3d at 196; Pappas v. Giuliani 290 F.3d 143, 146 (2d Cir.2002). In this respect, we only note that, in order to find that the plaintiffs’ float participation did not involve speech on a matter of public concern, we would necessarily have to find clear error in the district court’s factual finding that one of the aims of the float was “to comment on the future racial integration of Broad Channel.” Locurto, 269 F.Supp.2d at 385. It goes without saying that such social commentary, if actually an aim of the float, would be “a subject of general interest and of value and concern to the public.” Roe, 543 U.S. at 83-84, 125 S.Ct. 521; see Rankin, 483 U.S. at 387, 107 S.Ct. 2891; see also Connick, 461 U.S. at 148 n. 8, 103 S.Ct. 1684 (describing racial discrimination as “a matter inherently of public concern”).
Assuming, therefore, that the plaintiffs were speaking on a matter of public concern, we proceed to the second part of the Pickering framework.
B.
It is undisputed in this case that the plaintiffs’ expressive activity was the motivating factor behind their dismissals. Accordingly, the burden is on the Govern*176ment to make two showings: (1) that the employee’s activity was likely to interfere with Government operations and (2)-that the Government acted in response to that likely interference and not in retaliation for the content of the speech. See Jeffries II, 52 F.3d at 13; Heil v. Santoro, 147 F.3d 103, 109 (2d Cir.1998). If the Government carries its burden, a reviewing court then weighs the potential disruptiveness against the value of the speech to the plaintiff. See Heil, 147 F.3d at 109.
The district court held that the defendants did not, in fact, first suspend and then dismiss the plaintiffs in response to any reasonable concern for disruption of NYPD and FDNY operations but rather, and distinctly, “in response to the content of their speech and for reasons of public perception and the political impact expected to flow therefrom.” Locurto, 269 F.Supp.2d at 395; see also id. at 402 n. 23. Several factual findings motivated the district court’s conclusion. Crucial to the district court’s analysis was its determination that Giuliani decided to dismiss the plaintiffs on or about September 10, 1998 — that is, before the identities of the individuals who participated in the float were known, before the administrative hearings were held, and without significant input from anyone within the City’s African-American community. Id. at 391-92.
We find no clear error in the district court’s holding that Giuliani made a decision on or about September 10, 1998 that, if the plaintiffs’ involvement in the float was as originally described, they would be fired. The trial record includes ample evidence to this effect. Giuliani was quoted in an article that ran on September 11, 1998 as saying that any City employee involved in the float would be fired. The next day, he was quoted as saying that, though the plaintiffs “technically” were suspended, they would never be reinstated unless he was ordered to do so by the United States Supreme Court. When he took the stand, Giuliani did not dispute that he made either of these statements. Tr. at 186, 189-90, 211. As the district court noted, Giuliani specifically testified that he was “not sure” whether a decision to fire the plaintiffs was made on September 10,1998. Tr. at 224.
Giuliani argued on the stand that his statements could not be taken literally because the plaintiffs would have been reinstated had the hearing outcome been different, and that he did not, in any event, legally have the power to fire the plaintiffs. Tr. at 225. But clear error review sharply limits the extent to which we may second-guess the district court’s determinations with respect to witness credibility. See, e.g., Phoenix Global Ventures LLC v. Phoenix Hotel Assocs., Ltd., 422 F.3d 72, 76 (2d Cir.2005) (per curiam) (“[C]lear error review mandates that we defer to the district court’s factual findings, particularly those involving credibility determinations.”). And, although Giuliani did not have the legal authority to fire the plaintiffs, he did have the authority to fire Safir and Von Essen. Von Essen did not deny telling Steiner and Walters on September 11, 1998 that he did not wish to fire them but that his “hands were tied.” Tr. at 366-67. Given that Von Essen was empowered to accept or reject the recommendations of the ALJ, it was not clearly erroneous for the district court to conclude that it was Giuliani who was tying his hands. See Locurto, 269 F.Supp.2d at 390 (“[I]t would stretch the limits of common sense to conclude that these two (2) nominally independent Commissioners who served at the Mayor’s pleasure would not have understood the consequences of their defiance of the Mayor on an issue as to which he so strongly indicated his preference.”).
*177We disagree, however, with the district court’s legal conclusion, based largely on the timing of the firing decision, that the dismissals were retaliatory or otherwise improper.6 The motive the district court attributed to the defendants encompasses, in effect, two different rationales, which in the court’s view were both distinct from any putative concern over disruption: (1) that Giuliani determined to fire the plaintiffs out of hostility toward the content of their speech, and (2) that in firing the plaintiffs his motivating concern was his political image.
The court recited several bases for skepticism that the dismissals were motivated by concern over disruption. First, Giuliani’s comments about firing “any police officer, firefighter, or other city employee” came before he knew the identities of the float participants, and so reflected an indifference to the particular job function that such employee might perform. The court said that the lack of any distinction between employees, such as police officers, whose jobs involved significant public contact, and those whose jobs did not involve such contact “undercuts the contention that his statements were motivated primarily by a concern for civil unrest and/or minority recruiting in the police and fire departments.” Locurto, 269 F.Supp.2d at 391-92. Rather, the district court said, the true motivation for the plaintiffs’ termination was Giuliani’s negative feelings towards the content of the float, as evidenced by his terming the float a “disgusting display of racism.” See id. at 392.
Second, the district court noted that Giuliani admitted to having concerns over the public’s perception of his actions, reflected in his testimony that he “wanted people to know that ... I agreed with their reaction, that this was a horrific incident and that these people had forfeited, in my view, their right to wear the uniform.” Tr. at 196. The district court found it conspicuous and relevant that these comments regarding the public’s perception came in the immediate aftermath of a highly public controversy over Giuliani’s handling of the Million Youth March. The district court did not find persuasive Giuliani’s denial that the Million Youth March had any role in his decision with respect to the float. In this respect, the court noted that Von Essen had written in his autobiography that Giuliani was “sensitive to the constant accusations of racism” made against him and the police. Locurto, 269 F.Supp.2d at 392 (quoting Thomas Von Essen, Strong of Heart: Life and Death in the Fire Department of New York 140 (2002)).
Third, the district court considered relevant the fact that the NYPD had not dismissed any officer for racially offensive speech or expression at least since 1991, opting instead for more lenient penalties. The district court suggested that, were the defendants motivated by concern for “interdepartmental friction, diminished civilian confidence and future legal liability,” other officers involved in racist speech would have been punished more severely. Id. at 393.
Finally, the district court said that any avowed concern over disruption was undermined by Giuliani’s handling of the fatal shooting of unarmed African immigrant Amadou Diallo in February 1999. Despite widespread public condemnation of the officers involved in the Diallo shooting and *178attendant charges of racism hurled at the NYPD, Giuliani and Safir supported reinstatement of the officers. Id. at 394-95.
We have no doubt that, in considering how to respond to the plaintiffs’ actions, Giuliani, Safir, and Von Essen were driven largely by concerns over the public perception of the NYPD and FDNY. Where we part ways with the district court is in our recognition that the Government may, in some circumstances, legitimately regard as “disruptive” expressive activities that instantiate or perpetuate a widespread public perception of police officers and firefighters as racist.
Three of our circuit’s cases — Jeffries II, Pappas, and Melzer — give us particular guidance in reaching this conclusion. In Jeffries II, we upheld a jury verdict that permitted City College to reduce the term as department chair of a professor who made controversial public statements about Jews. We noted that prior precedents of our Court had established that the Government could not censure an employee for speaking on issues of public concern “unless the speech actually disrupted the employer’s operations.” Jeffries, 52 F.3d at 12 (citing Jeffries v. Harleston, 21 F.3d 1238, 1245 (2d Cir.1994) (Jeffries I)). The Jeffries II Court acknowledged, however, that this holding was undermined by the Supreme Court’s decision in Waters, in which a Court plurality emphasized that the Court has “given substantial weight to government employers’ reasonable predictions of disruption.” Id. at 13 (quoting Waters, 511 U.S. at 673, 114 S.Ct. 1878). The Jeffries II panel explained that, under Waters, “the extent of the injury caused by the employee’s speech need not be actual; rather the government’s burden is just to show that the speech threatened to interfere with government operations.” Id. (emphasis added).
Given this language, the question in the case before us becomes one of defining a reasonable threat of disruption in the context of the jobs of police officers and firefighters. We considered this question in Pappas, in which we permitted the NYPD to dismiss an officer who worked on Department computers and who had anonymously replied to a series of mail solicitations from charities with racist and antisemitic diatribes, and who, in the process, had generated media attention. Judge Le-val’s majority opinion explained with characteristic elegance the unique relationship between a police department and the public it serves:
The effectiveness of a city’s police department depends importantly on the respect and trust of the community and on the perception in the community that it enforces the law fairly, even-handedly, and without bias. If the police department treats a segment of the population of any race, religion, gender, national origin, or sexual preference, etc., with contempt, so that the particular minority comes to regard the police as oppressor rather than protector, respect for law enforcement is eroded and the ability of the police to do its work in that community is impaired. Members of the minority will be less likely to report crimes, to offer testimony as witnesses, and to rely on the police for their protection. When the police make arrests in that community, its members are likely to assume that the arrests are a product of bias, rather than well-founded, protective law enforcement. And the department’s ability to recruit and train personnel from that community will be damaged.
Pappas, 290 F.3d at 146^47 (internal citation omitted). Police officers and firefighters alike are quintessentially public servants. As such, part of their job is to safeguard the public’s opinion of them, *179particularly with regard to a community’s view of the respect that police officers and firefighters accord the members of that community. Dissenting in Pappas, Judge Sotomayor emphasized that Pappas, an information systems employee, was unlike “[a] police officer walking the beat.” Id. at 156 (Sotomayor, /., dissenting). Because someone who walks a beat “is often the representative with whom the public interacts[,][i]t is not difficult to see how such an officer who expresses racist views in certain situations could damage the efficient operation of the NYPD.” Id.; see McEvoy, 124 F.3d at 103 (“The more the employee’s job requires confidentiality, policymaking, or public contact, the greater the state’s interest in firing her for expression that offends her employer.” (quoting Craig D. Singer, Comment, Conduct and Belief: Public Employees’ First Amendment Rights to Free Expression and Political Association, 59 U. Chi. L.Rev. 897, 901 (1992)) (emphasis added)); see also Rankin, 483 U.S. at 390-91, 107 S.Ct. 2891.
More recently, in Melzer, we reiterated that a Government employer may, in termination decisions, take into account the public’s perception of employees whose jobs necessarily bring them into extensive public contact. In permitting the New York City Board of Education to dismiss Melzer for his professed pedophilia and involvement in NAMBLA, we considered “central to our review” the fact that Melzer was a school teacher, a position that “by its very nature requires a degree of public trust not found in many other positions of public employment.” Melzer, 336 F.3d at 198-99. Melzer argued that permitting the public’s reaction to his NAM-BLA-related actions to influence the Board’s decision would amount to a “heckler’s veto,” see id. at 199, which the Supreme Court has long regarded as generally impermissible. See Feiner v. New York, 340 U.S. 315, 320, 71 S.Ct. 303, 95 L.Ed. 295 (1951) (“[T]he ordinary murmurings and objections of a hostile audience cannot be allowed to silence a speaker.”); Terminiello v. City of Chicago, 337 U.S. 1, 4, 69 S.Ct. 894, 93 L.Ed. 1131 (1949) (“[Fjreedom of speech, though not absolute, is nevertheless protected against censorship or punishment, unless shown likely to produce a clear and present danger of a serious substantive evil that rises far above public inconvenience, annoyance, or unrest.” (internal citation omitted)). The Melzer panel rejected the “heckler’s veto” argument as less applicable to the relationship between Melzer and high school parents, who were not “outsiders seeking to heckle Melzer into silence, [but] rather ... participants in public education, without whose cooperation public education as a practical matter cannot function.” Melzer, 336 F.3d at 199; cf. Tindle v. Caudell, 56 F.3d 966, 971 (8th Cir.1995) (“Because police departments function as paramilitary organizations charged with maintaining public safety and order, they are given more latitude in their decisions regarding discipline and personnel regulations than an ordinary government employer.”).
Our cases make clear, then, that the district court’s dichotomy between the defendants firing the plaintiffs “out of a concern for potential disruption” as against their doing so “for reasons of public perception” or “in response to the content of plaintiffs’ speech,” Locurto, 269 F.Supp.2d at 395, is a false one. Where a Government employee’s job quintessentially involves public contact, the Government may take into account the public’s perception of that employee’s expressive acts in determining whether those acts are disruptive to the Government’s operations. Moreover, as mentioned earlier, the disruption need not be actual; the Government may legitimately respond to a-reasonable prediction of disruption.
*180All that said, it still must be the case, of course, that the concern for disruption, rather than some other, impermissible motive, was the actual reason for the adverse employment action. See Sheppard v. Beerman, 94 F.3d 823, 827 (2d Cir.1996). And, even after demonstrating that a concern for disruption was its true motivation, the Government must also persuade a court that its interest in preventing disruption outweighed the employee’s individual free speech interests. See Jeffries II, 52 F.3d at 13.
In the present case, the evidence in the record is overwhelming that, in discharging the plaintiffs, the defendants were motivated primarily by a concern that the public, and particularly members of minority communities, would regard the NYPD and FDNY as racist. This is, of course, a question of fact, and as a result, it is one in which we review the district court’s determination for clear error. See Locurto I, 264 F.3d at 167. Giuliani’s reported comments at the time the controversy initially surfaced are especially telling. In the context of the record as a whole, his statement that adverse actions would be taken against “any police officer, firefighter or other city employee,” see Locurto, 269 F.Supp.2d at 391-92, cannot be read as suggesting that Giuliani was indifferent to whether the employee’s job involved public contact. Rather, as mentioned in the very article from which the quote derives, Giuliani knew at the time he made the statement that the suspected float participants were police officers and firefighters. Indeed, the quote itself indicated as much in its express reference to conversations Giuliani had with Safir and Von Essen. See Mustain, supra, at 7. Giuliani explained himself in contemporaneous remarks, saying that “[pjolice officers [and] firefighters carry a very heavy responsibility ... to treat people fairly. That responsibility cannot be placed in doubt.” Id. (second and third alterations in original). The next day, he was quoted saying, “I’m not going to take the responsibility of keeping [Locurto] on the police force and then three years from now he hurts somebody and somebody wants to know why he wasn’t removed.” Roane, supra, at 51. Under the circumstances, the fact that, in a statement in which he specifically singled out police officers and firefighters, Giuliani tacked on “or other city employee” simply cannot bear the weight the district court placed on it.
Moreover, the fact that Giuliani viewed the plaintiffs’ speech as “a disgusting display of racism” does not, without more, mean he fired the plaintiffs in “retaliation” for engaging in racist speech. Indeed, if Giuliani’s inclination were to fire City employees who engaged in racist speech, it would be difficult to explain why, as the plaintiffs themselves point out, the NYPD had never during Giuliani’s tenure as may- or dismissed a police officer for this reason. See Locurto, 269 F.Supp.2d at 392-93. The district court recounted three incidents from the 1990s in which police officers used racial slurs in the course of their work but received relatively lenient penalties. See id. at 393 n. 16. And the parties submitted to the district court a comprehensive breakdown of cases in which officers had been charged with racial misconduct. See Joint Pre-Trial Exhibit, Dec. 8, 2002. Notably, there is no indication in the record that any of these incidents generated nearly the notoriety of the plaintiffs’ float, which was labeled “Racist Float” on the six o’clock news and which was covered extensively in the print media. The capacity for a particular incident to generate public attention is obviously highly relevant to the City’s assess*181ment of the incident’s disruptive effects.7 That is to say, the evidence is overwhelming that the content of racist speech did not bring about dismissal, in the absence of notoriety which would reasonably be seen to affect the perception of the speaker and the Government in the public eye.
Giuliani’s trial testimony was wholly consonant with his being motivated by the plaintiffs’ actions bringing discredit upon the police and fire departments within minority communities. Giuliani said that he was concerned that the plaintiffs “had ... acted in a highly-unprofessional way, in a way that would do great damage to the police department and the fire department, damage to the city, disrespect to the uniform, create disruption, and [have] consequences for other police officers and firefighters [and] put in question the ability of police officers and firefighters to act impartially with regard to minorities or people of different race[s].” Tr. at 179-80. He also expressed concern about the impact the float’s notoriety would have on minority recruiting, particularly within the FDNY. See Tr. at 180,182-83.
The district court was, of course, free to place diminished weight on this testimony or even to disbelieve it outright, but its conclusion that Giuliani’s motive was impermissible must itself be supported by evidence in the record. See Fed.R.Civ.P. 52(a). Although Rule 52(a) demands great deference to a trial court’s factual findings in general, and to its credibility determinations in particular, we have not hesitated to find clear error “where the court has failed to synthesize the evidence in a manner that accounts for conflicting evidence or the gaps in a party’s evidentiary presentation.” Doe v. Menefee, 391 F.3d 147, 164 (2d Cir.2004). Similarly, we have found clear error where, for example, “the trial court incorrectly assessed the probative value of various pieces of evidence, leading it to rely on speculation, and where the court failed to weigh all of the relevant evidence before making its factual findings.” Id. (citing United States v. Rizzo, 349 F.3d 94, 100-02 (2d Cir.2003); Ortega v. Duncan, 333 F.3d 102, 107 (2d Cir.2003)).
We have already said that the district court’s discomfort with Giuliani’s worries over the general public perception of the float was misplaced. The only remaining, arguably impermissible, motive attributed to Giuliani was a concern over the “political impact” of the public reaction to the float. There are two distinct senses in which Giuliani’s motive could be described as “political.” First, he could have been concerned about the public perception of the police and fire departments and of the City. As mentioned, this concern is, in itself, an entirely legitimate one in the context of deliberate public acts by police officers and firefighters that are perceived as racist. Second, Giuliani could have been more specifically motivated by concerns over his personal popularity and/or his ability to continue to pursue his political agenda or win future elections. This would, of course, be an impermissible reason for dismissing the plaintiffs. But the only evidence in the record that, arguably, evinces this motive is the fact that Giuliani *182had recently been criticized over his handling of the Million Youth March. And that evidence is questionable, for Yon Essen’s book, which the district court said “tied [the March controversy] to the decision-making process in this case,” Locurto, 269 F.Supp.2d at 392, instead provides rather strong evidence that the “political impact” Giuliani sought to avoid was precisely the legitimate one to which he testified — the public perception that New York City police officers were racist.
In short, stripped of the analysis undermined by Jeffries II, Pappas, and Melzer, and in the light of substantial contrary evidence, the district court’s conclusion that Giuliani ordered the plaintiffs’ dismissals for improper motives rests on too thin a reed, one that “on the entire evidence” leaves us “with the definite and firm conviction that a mistake has been committed.” Anderson v. City of Bessemer City, 470 U.S. 564, 573, 105 S.Ct. 1504, 84 L.Ed.2d 518 (1985) (quoting United States v. U.S. Gypsum Co., 333 U.S. 364, 395, 68 S.Ct. 525, 92 L.Ed. 746 (1948)). We find, instead, that the motive for the defendants’ actions was a concern for the potential disruption the plaintiffs’ activities would cause to the NYPD and FDNY, in particular by engendering and perpetuating a public perception of those Departments as racially insensitive.
Moreover, we have no difficulty concluding, contrary to the district court, see Locurto, 269 F.Supp.2d at 396, that the defendants’ concern for disruption was reasonable at the time. The Supreme Court has said that “[w]hen close working relationships are essential to fulfilling public responsibilities, a wide degree of deference to the employer’s judgment is appropriate .... [W]e do not see the necessity for an employer to allow events to unfold to the extent that the disruption of the office and the destruction of working relationships is manifest before taking action.” Connick, 461 U.S. at 151-52, 103 S.Ct. 1684; see Arnett v. Kennedy, 416 U.S. 134, 168, 94 S.Ct. 1633, 40 L.Ed.2d 15 (1974) (Powell, concurring) (“[T]he Government, as an employer, must have wide discretion and control over the management of its personnel and internal affairs. This includes the prerogative to remove employees whose conduct hinders efficient operation and to do so with dispatch.”). Whatever the plaintiffs’ intentions, the message their actions conveyed was, from the vantage of our nation’s history, sadly unoriginal. It was as obvious on September 10, 1998 as it was after the administrative hearings were held that police officers and firefighters who deliberately don “blackface,” parade through the streets in mocking stereotypes of African-Americans and, in one firefighter’s case, jokingly recreate a recent vicious hate crime against a black man, might well damage the relationship between the NYPD and FDNY and minority communities. See, e.g., Pappas, 290 F.3d at 146-47; Pappas, 290 F.3d at 156 (Sotomayor, J., dissenting); Tindle, 56 F.3d at 973.
The district court placed great weight on the fact that the threatened disruption was “external” rather than “internal.” See Lo-curto, 269 F.Supp.2d at 398. To the extent that such a distinction in the specific context of community perceptions of police officers and firefighters as racist may have survived Pappas, it did not survive Melzer. The members of the African-American and other minority communities whose reaction to the float the defendants legitimately took into account, like the parents in Melzer, cannot properly be characterized as “outsiders seeking to heckle [the plaintiffs] into silence.” Melzer, 336 F.3d at 199. Rather, effective police and fire service presupposes respect for the members of those communities, and the defen*183dants were permitted to account for this fact in disciplining the plaintiffs.
C.
Our determination that the defendants were motivated by a reasonable concern for the potentially disruptive effects of the plaintiffs’ actions does not end our inquiry. A plaintiff alleging an adverse employment action in violation of the First Amendment can prevail even over an employer who took the action for legitimate reasons if the employee’s expressive interests outweigh the employer’s interest in preventing disruption. See -Jeffries II, 52 F.3d at 13. The plaintiffs’ expressive interests in the instant case are not insubstantial. The district court found that their participation in the parade float was, in part, performance commentary-on the future racial integration of Broad Channel, see Locurto, 269 F.Supp.2d at 385, and we see no reason to disturb this finding. Whatever our own views of the quality and prudence of the plaintiffs’ chosen means of expression, commentary on race is, beyond peradventure, within the core protections of the First Amendment. See Jeffries I, 21 F.3d at 1245-46 (“First Amendment protection does not hinge on the payability of the presentation; it extends to all speech on public matters, no matter how vulgar or misguided.”).
We nonetheless find that the defendants’ interest in maintaining a relationship of trust between the police and fire departments and the communities they serve outweighed the plaintiffs’ expressive interests in this case. If the NYPD and FDNY have any greater interests than these, they are few. See Pappas, 290 F.3d at 146-47. And the speech at issue in this case was not merely of passing interest to members of the African-American community; rather, they were the very objects of the plaintiffs’ derision. The First Amendment does not require a Government employer to sit idly by while its employees insult those they are hired to serve and protect. Under the circumstances, “an individual police officer’s [or firefighter’s] right to express his personal opinions must yield to the public good.” Id. at 147.8
Conclusion
We do not today endorse Justice Holmes’s widely discredited dictum that one has “a constitutional right to talk politics, but . -.. has no constitutional right to be a policeman.” McAuliffe v. Mayor & Bd. of Aldermen, 155 Mass. 216, 29 N.E. 517, 517 (Mass.1892). One does, of course, have a First Amendment right not to be terminated from public employment in retaliation for engaging in protected speech. But one’s right to be a police officer or firefighter who publicly ridicules those he is commissioned to protect and serve is far from absolute. Rather, it is tempered by the reasonable judgment of his employer as to the potential disruptive effects of the employee’s conduct on the public mission of the police and fire departments. We find, in this case, that the judgment of the defendants was reasonable, that it was the clear motive for the plaintiffs’ dismissals, and that it outweighed the plaintiffs’ individual First Amendment interests in participating in the “Black to the Future” float.
The judgment of the district court is therefore Reversed and the case is Remanded with instructions to enter judgment in favor of the defendants on the plaintiffs’ federal claims. The state claims *184are dismissed without prejudice. Each party will bear its own costs.
. The reference, one presumes, is to a line attributed to Malcolm X — “We didn't land on Plymouth Rock, Plymouth Rock landed on us,” see Malcolm X (40 Acres & A Mule Film-works 1992) — and not to the title song from Cole Porter’s Anything Goes, which contains a similar line, see Paul Whiteman with Ramona Davies, Anything Goes (RCA Victor 1934) ("Times have changed / and we’ve often rewound the clock / since the Puritans got a shock / when they landed on Plymouth Rock. / If today, / any shock they should tty to stem, / ‘stead of landing on Plymouth Rock, / Plymouth Rock would land on them.’ ”).
. Only three remedial options were available to the ALJ: reprimand, loss of 10 days' pay, or dismissal from the Fire Department. See New York City Admin. Code § 15-113. The ALJ said that loss of three months' pay would be more appropriate than dismissal, but that loss of 10 days' pay was too lenient. Steiner, Nos. 559 & 560/99, at 28-29.
. ALJ Maldonado's denial of Steiner's and Walters's request to call Von Essen might have been motivated by her suggestion that the motivating factor behind the suspension decision was "not in dispute.” To the extent the agency considered this issue not to be contested, the district court's findings as to Von Essen's motivation are not "identical to a material issue necessarily decided by the administrative agency in a prior proceeding,” Jeffreys, 769 N.Y.S.2d 184, 801 N.E.2d at 407, and therefore are not precluded by the findings of the administrative hearing.
. This is not to say that a neutral arbitrator at a pre-termination administrative hearing is a requirement of due process. As we held in Locurto I, a pre-termination hearing before a non-neutral adjudicator may yet comport with due process "where the state affords *172plaintiff, subsequent to his termination, a full adversarial hearing before a neutral adjudicator.” Locurto I, 264 F.3d at 174. But, contrary to the defendants’ argument, the fact that the availability of post-termination review via an Article 78 proceeding is sufficient to satisfy due process does not mean that it is sufficient to confer collateral estoppel effect upon pre-termination hearing findings. The cases the defendants cite for this proposition hold only that, under New York law, the opportunity to appeal an adverse finding is necessary for collateral estoppel to attach; they do not hold that it is sufficient. See Fletcher v. Alex, Inc., 68 F.3d 1451, 1458 (2d Cir.1995) (citing People v. Medina, 208 A.D.2d 771, 617 N.Y.S.2d 491, 493 (App.Div.2d Dep't 1994)); Crespo v. New York City Police Comm’r, 930 F.Supp. 109, 114 (S.D.N.Y.1996); Williams v. Moore, 197 A.D.2d 511, 602 N.Y.S.2d 199, 201-02 (App.Div.2d Dep’t 1993).
. Ceballos v. Garcetti, 361 F.3d 1168 (9th Cir.2004), cert. granted, 543 U.S. 1186, 125 S.Ct. 1395, 161 L.Ed.2d 188 (2005), a First Amendment retaliation case in which the Supreme Court recently reheard oral argument, is also of this sort.
. As we noted in Locurto I, although the defendants' intent is a factual question, which we review for clear error, whether that intent ultimately amounts to "retaliation'' forbidden by the Constitution is a question of law, which we review de novo. See Locurto I, 264 F.3d at 166, 167; see also Johnson v. Ganim, 342 F.3d 105, 114-15 (2d Cir.2003); Gorman-Bakos v. Cornell Coop. Extension, 252 F.3d 545, 557-58 (2d Cir.2001).
. And, although it is true that the Amadou Diallo controversy also generated notoriety and racial tension within the City, the similarity to this case ends there. Whatever one's opinion of the actions of the officers in the Diallo case, it was the position of the NYPD and the Mayor that the officers were acting within the scope of their duties, and it is undisputed that the officers were acquitted in court of any wrongdoing. Locurto, 269 F.Supp.2d at 393-94. It is not inconsistent, under the circumstances, for Giuliani not to support dismissal of those officers. That is quite apart from the questionable relevance to this case of Giuliani's response to an incident that occurred months later.
. Because the Pickering balancing test weighs in favor of the defendants, we need not reach and do not decide whether the individual defendants would otherwise be entitled to qualified immunity.