The Australian Consulate-General in New York and the Embassy in Washington are the two obvious places I could go to get a new passport.
New York (also closed on Monday) requires an appointment but have availability. Washington is just walk-in.
I figured the embassy is likely to have the quickest turn around so I decided to go there and booked a 6am one-way flight from Boston to DC for Tuesday morning.