Why is "tymi kobietami" in the instrumental case instead of genitive? I thought that words following "z" should be in the genitive, but I guess that's not always the case?
The word "z" in Polish might mean different things, depending on the context. Sometimes it means "from", sometimes it means "with". In the first situation, we use genitive, in the second one we use the instrumental case. Let me give you an example, so you can see how it works: "Pochodzę z Polski" - "I come from Poland" (you use genitive). But "Jestem silnie związany z Polską" - "I'm strongly connected with Poland" ( you use the ablative).
Which meaning of "work with" is this? Does it mean they are coworkers, that these women employ him, or that they're cooperating?
Options 1 and 3 for sure fit here, the second one... is possible, but it would be better to say "dla tych kobiet" (for these women).