With a slew of hijacked and compromised Gmail accounts from people I know, I started thinking about an easy way to protect yourself from it. I did come up with a free but not so simple solution:
1. Sign up for the free Google Apps for Domain package.
2. Create a special user for administrating the domain whose password and reset credentials are different from your regular ones. Make sure that the secondary email address points somewhere else like your phone (see here for a list of SMS gateways).
3. Setup your regular account and make sure NOT TO GIVE IT domain admin privileges or same password.
4. If you account gets hijacked or compromised, whip out the special domain administrator account, login and reset your regular account password.
UPDATE: Of course, don't forget backup services like Backupify.