Why don't we utilize
first-seen-safe RBF then? If the problem is to annoy the other party/parties by cancelling the CoinJoin or channel opening transaction, we can give a solution by accepting only transactions that spend to the same outputs, equal or greater amounts.
This was the primary way of RBF at that time when there were plans to either get FSS-RBF or Opt-in RBF on the network. There are many different risks and hassle with FSS-RBF, namely with it being subjective to the different miners and that it provides a false sense of security with no security benefits whatsoever. It was only adopted by Discus Fish (AKA. F2Pool) and dropped shortly afterwards. RBF (Opt-in or not) does not prevent fraud or anything like that, merely making it slightly harder for the average person but doesn't make them immune.
I don't foresee it to be a problem. Users generally do update their nodes, and currently 18% of the network runs 0.23 and 50% of the network runs 0.22. The number of hops that it takes to reach a miner should still be acceptable and you shouldn't have a case where it gets stuck due to nodes stopping the propagation of the transaction. Miners are generally very well connected to a myriad of nodes. However, the main concern should be whether the miners are willing to change their policy and start accepting these kind of transactions.
Peering should be a no issue because it is usually done by recognizing the service flags of their peers. It shouldn't be too difficult to have a service flag where the node attempts to connect to another which has full-rbf enabled.