Assuming that you're actually moving here, not just here for a visit: No specific suggestions, but come about 2-3 weeks before your expected move and scour CL. Be sure to start your conversation with brokers by mentioning your pets and repeat frequently. You don't need to be tied to a specific broker, remember they represent the landlord. You may be more likely to find a pet friendly place if you look in Queens/Jersey/BK. If you're willing to pay a bit more, there are lots of new towers in downtown BK and some are pet friendly.
If you're just coming for a visit look for sublets on CL, there are often lots. No one will rent to you without meeting you in person though.