Verification w/ Public key recovery is never going to be faster than normal verification however it is only marginally slower.  I benchmarked it a while back and it was only about 5% overhead to do pubkey recovery.

Changing the txn format would require a hard fork so it is unlikely that is going to happen but the advantage of pubkey recovery is trades storage for time.  A typical 2in, 2out P2PkH transaction is 373 bytes with compressed keys (437 bytes w/ uncompressed keys).  The same transaction without pubkeys would be 309 bytes so a savings of 17% to 29% in exchange for 5% slower verification.

Hashing is extremely fast so performing 4 hashes vs 1 hash is negligible but that overhead can be removed by adding a flag to the signature to indicate which form to use when recovering the PubKey.

    0x02 = compressed even
    0x03 = compressed odd
    0x04 = uncompressed even
    0x05 = uncompressed odd

This really only saves space in P2PkH transactions. For P2SH (i.e. multisig) the script contains full pubkeys already. While in theory new OP_CODES could be used to support multisig using key hashes there isn't much space saved.

If we were ever going to redesign txns I would go with Schnorr signatures as they support thresholding signing.  That would mean only one signature per txn vs one or more signatures per input as used now.