How big are the dogs/how much space do they need? Depending on budget you can get a small backyard in Hoboken or JC. Private backyard costing more than one shared with the building.

Also how are they with other dogs? Since most people don't have yards there are some dog parks scattered around Jersey City, Hoboken, and NYC itself.