Fine, so I got the message, reduced the game to "novice" difficulty and actually survived the first fire fight. Hurrah.
Now I need to contact the rebels in La Omerta - but I don't see anyone who'll talk to me. In the western area of the town there is only a woman who talks about feeding her children, and a kid who says his mother doesn't want him to talk to strangers, and in the eastern side, only dmitri, who won't say a thing. What am I missing?

I'm not sure about needing high leadership.
If I remember correctly it didn't matter much in the original.
If it does matter however and you don't have high enough leadership, you could try the following (save first):
- start a talk with Fatima
- press the Give button and give her the letter
If that doesn't work, ignore this quest and take Drassen, train militia, find the pilot, take the SAM-site, train militia.
Train militia with the mercs with the highest intelligence as they increase leadership the fastest.