Advantages:

  Available to SPV nodes with no change to the network protocol

  Available after headers downloaded, before full block data is available

  Once well past a fork, allows all block validation except validation against the UTXO to happen in parallel, out-of-order, independent of any other block.

Disadvantages:

  Not monotonically increasing

I think discussion about transactions in the memory pool are just a distraction: no matter what criteria is used (timestamp, height, median time), a blockchain re-organization could mean the validity of transactions you've accepted into the memory pool (if you're accepting transactions that switch from valid to invalid at the consensus change -- Core tries hard not to do that via IsStandard policy) must be re-evaluated.

I don't strongly care if median time or block timestamp is used, I think either will work. I don't like height, there are too many cases where the time is known but the block height isn't (see, for example, the max-outputs-in-a-transaction sanity check computation at line 190 of bitcoin-tx.cpp -- bitcoin-tx.cpp has no idea what the current block height is).