In a very similar situation at the moment,
Based on several weeks of deploying DMARC:
Know your mail flows and which mail servers send mail from your environment or on your behalf. Start by updating your SPF records accordingly and remember that all domains AND sub-domains need to have their own SPF records.
SPF might still fail due to various reasons (mobile users, remailers etc.) My view is that the way to bypass this on the short-term is to start DKIM signing ASAP for your main domain AND your subdomains.
In case you are working with 3rd parties, either get them to channel their mail flows through your own mail servers, or liaise with them to ensure they are DKIM-savy enough, and build a process to regularly rotate their DKIM public key(s) in your DNS.
Be patient with tightening your policy (I also had planned to follow Google's ramp-up). It is worth taking the time to delve into the DMARC reports and understand why exactly SPF/DKIM/DMARC failed. In a lot of cases, these are actual spoofs. You might discover mail flows which you were not even aware of. Use open source parsers to visualize your reports or send them to some log management system to facilitate the analysis. Or outsource the analysis.
Remember to apply inbound DMARC checking as well. Let everything through in a first phase, then progressively enforce the sender policy. You could e.g. quarantine mails that should be rejected, then actually reject them.
There is an element of risk in enforcing DMARC or publishing a DMARC policy other than p=none, but the reports actually give you a LOT of information and allow for a controlled implementation. It is essential to know your mail flows and who administrates them. Also, test test test as much as possible with dummy mail flows (netcat is your friend)!
Finally, remember that AOL et al. only send you the results of their DMARC checking of mails sent from your domain (or someone who spoofs it). So if a test is flagged as failed, it indicates a problem on your side, not theirs :)