Decentralization between cryptocurrency is easy. The problem is fiat; you cannot really have a proper contract with fiat without trusting the other party. So unfortunately, a certain degree of trust is still needed there.

https://bisq.network/ is probably the closest thing to decentralized exchange up to date.