Presumably Gmail already has anti-spam features which trigger based on domain name etc.
They could add anti-phish features which force confirmation before clicking a link to an uncommon domain. Startups could pay a nominal fee to get their domain reviewed and whitelisted.
In a world where those sending email were consistent, the user could control the whitelist. 'This link is from a domain you've clicked through X times, do you want to click through? Yes / Yes and don't ask again'
If it's new, you should be more cautious. Except even those companies that should know better need you to link through 7 levels of redirect tracking, and they're always using a new one.
A user for example. By default nothing would be in the whitelist.
Then you would add things to the whitelist manually. Since it's not that frequent this needs to be done, that probably would be a useful extra step to stop phishing.
Do you think there would be the time to properly review applications to get on the whitelist?