Well you cant use a 4096 bit private key with ECDSA as used by bitcoin and 4096 bit RSA keys are not useless even though they only provide a security level of 128 bit[1].
Yes, I was referring in the contect of ECDSA not other algos.
True calculating a bitcoin address from a private key is not an elemantary operation. It would make an attack even slower for an unused address. I dont think it matters much though. 2160 or 2128 are both very large search spaces.
[1] might not be the exact correct value, cant find a table atm.
Yes so an unspent address is 160 bit + work of doing the other operations.
However a spent address has only ECDSA separating your money from the thief, and it's very scary. So I think public keys should be treated confidential as well as private keys, in the sense that newbies should not reveal them to strangers.