"Wrong! Random people will totally verify key fingerprints when they're logging into Google Mail at Starbucks! After all, that's what every sysadmin does with SSH, right!"
I think you think that "Trust On First Use" means "automatically accept keys the first time you hit a site". In fact, that's only true in practice. Presumably everyone's going to get the "Watch Out! This Could Be Iran!" dialog from their browser, too.
Theoretical models that have no practicality in a given real life context aren't worth discussing as a solution.