Relays shouldn't have to be trusted.
It's not really true that you need a full node to verify OTS timestamps, you can use an SPV-like trust model where you just have the Bitcoin block headers and check their POW. The headers are just 80 bytes per block.