New is new, it's always worth getting a new product. You never know about used phones, how much are they used, problems etc unless the seller is a trusted guy.!
just a little comparison
Xperia Z over S4:
1.Better Design
2.Better Camera
3.Water resistant
4.Better GPU (compared to S4 i9500)
5.Way better built quality
S4 over Xperia Z:
1.Better screen as per reviews
2.Better CPU(If i9505 model)
3.Better software support
Now it totally depends on you. BTW Xperia Z is a bit old model. Xperia Z1, Z1 compact and Z2 are released after this, so it's a bit old phone.