I find that validation rules tend to need the reverse (inverse?, converse?, contrapositive? ...something) of what I'd normally do in Apex.
If the expression in your validation rule evaluates to true, you get the validation error.
In your first example, both
City need to be blank to trip the validation rule. That lines up with your observation, and is different from what you say you want.
A shift in mindset can help here. Instead of thinking "what must this data be to be valid?", try to think "what must this data be to be invalid?"
Invalid data in this first case is when either
City are blank.
In your second case, data is invalid if
Email is blank, or (
Fax) are blank.
Writing out a truth table can also be helpful to understand if what you have meets your needs (and what needs to change if it's not working)
let x = email is blank
let y = city is blank
let z = fax is blank
let a desired result of false = validation does not fail, record can be saved
x y z | desired result
false | false | false| false
false | false | true | false
false | true | false| false
false | true | true | true
true | false | false| true
true | false | true | true
true | true | false| true
true | true | true | true
if x is true, validation should fail
if both y and z are true, validation should fail
that means our expression here is x || ( y && z)