"Rats with wings" = pigeons.
These are two colorful New York terms. The first ("sea gulls of the sink") has really just been used once. A spin-off "rats with--" term, "rats with antlers," has been used to describe deer.
3 October 1938, New York (NY) Times, pg. 17:
Curran Now Pens Praise of Roach
The Humble "Sea Gull of the Sink"
A nearly lyrical defens of cockroaches is the latest move by Deputy Mayor Henry H. Curran in the pleasant controvery arising from his flinty attitude toward a plea for playgrounds for the city's dogs.
"Alas, poor roach!" Mr. Curran laments. "Is there no little place in your heart for this industrious and peaceable member of the world's family of living things?"
Maintaining that the friendless insect is really the "sea gull of the sink, humble and faithful," the Deputy Mayor continues:...
9 April 1966, New York (NY) Times, pg. 18:
Henry H. Curran Is Dead at 88;
City's Former Chief Magistrate
As for cockroaches, in October of 1938, Mr. Curran -- having taken an adamant stand against those who wanted playgrounds for the city's dogs -- went on to ask about equivalent rights for cats and, ultimately, roaches.
The "sea gull of the sink," he insisted, was "humble and faithful."
22 June 1966, New York (NY) Times, pg. 59:
Commissioner Hoving (Parks Commissioner Thomas P. F. Hoving -- ed.) calls the pigeon "a rat with wings."
31 December 1967, New York (NY) Times, pg. 190:
To discourage pigeons, recently defined as rats with wings, I scatter millet and cracked corn for juncos and other sparrows in the heart of brush pile which is kept for this purpose.
Origin of the pigeon slur, "rats with wings"?
Excerpts from Screenplay, Stardust Memories, 1980
Note: The character of Sandy is played by that real-life pillar of virtue and morality (NOT!), Woody Allen.
DORRIE "What are you thinking about when you look out there?"
SANDY "Just, you know, all those people and, you know, how unhappy most of them are, and how...those terrible things they do to each other and, you know. How everything is...over so quickly and you don't have any idea...was it worth it or not."
. . . .
SANDY "What was that? What was that?"
DORRIE "Hey, that's so pretty. A pigeon!"
SANDY "Geez...no, it's not pretty at all. They're...they're...they're rats with wings."
DORRIE "They're wonderful. No! It's probably a good omen. It'll bring us good luck."
SANDY "No...no, get it out of here. It's probably one of those killer pigeons."
DORRIE "No, get something for it to eat. We can coax it down! What are you doing? Hey, wait!"
SANDY "You see, it's got a swastika under its wings."
DORRIE "It's wonderful. Not that.
SANDY "I just...I just want to guide it out of the apartment. Geez. I don't want a winged thing in my house."
23 January 1981, Washington (DC) Post, pg. A1:
"I think Woody likes to create phobias," she (actress Charlotte Rampling, co-star with Woody Allen in the film Stardust Memories -- ed.) says. "He's afraid of pigeons. 'They're rats with wings,'" he says.