This only works if mining is homogeneous throughout the network, which is very much not how Bitcoin exists today. Otherwise it is up to the policies of a few individual (large) miners how likely a transaction is to get mined, not an emergent property of network propagation.
Disagree. If nodes are following a policy of first seen, then the necessary attribute is an emergent property of network propagation.
If you are arguing that mining clients won't follow the sane rule of first seen, then you are arguing against the Bitcoin model of mutual incentive to hold the entire economic concept together.
The motivation behind replace-by-fee is not to just go and break things, as detractors argue. It is to make instant payments safer by removing the incentive to double spend. The reason being that if you can double spend by increasing the fee, the recipient can too. The result is a bidding war where the entire amount gets burned in fees, and you gain nothing, removing the incentive to double spend in the first place.
Whereas afaics (?), Todd's proposal doesn't help the recipient who already delivered the goods (the spender can burn up the recipient's payment out-of-spite just to destroy Bitcoin), which was the entire point of 0-confirmations in the first place.