In this case, I would say that it would depend on the type of application Bitcoin is being used for.
Absolutely. I referred to BitPay as an example of a company that would not want to do this.
For the "average user" (whatever that is!), I think you could use bitcoin safely with the certainty of 1000 valid last blocks. This is the logic of SPV wallets. The software could be pretty certain that the entire blockchain is valid, if the last 1000 blocks are valid and have valid poof of work. Building 1000 fake blocks is expensive. Obviously your node would verify these last 1000 blocks with multiple nodes on the network, so that a Sybil attack would be harder to pull off.
The software could then work backwards, from block 1001 from the top, all the way to the genesis block. The further down, and the more valid proof of work and valid transactions, the more certainty you have that everything is kosher.
This validation does not need to be done upfront, I don't think, for the majority of users. If it is done in a low priority side thread in the software, it could do this in the background while bitcoin is running and functional. It could display some progress indicator to show what it is doing, but even that would be optional.
I actually quite like this idea. I wonder why it would or would not work.