The second one doesn't seem excessively complicated and the latency could be mitigated by caching the CA for a reasonable period of time.

But if you're going to modify the protocol anyway then why not just put it in the protocol that a "server" certificate is to be trusted even if the peer server is initiating rather than accepting the connection? That's effectively what you would be doing by trusting the "server" certificate to authenticate the chain of trust for a "client" certificate anyway.