AD upgrade/refresh - what would you do?

If I understand correctly, out of those options, I'd personally go for option B (assuming this https://support.office.com/en-gb/article/How-to-prepare-a-non-routable-domain-such-as-local-domain-for-directory-synchronization-e7968303-c234-46c4-b8b0-b5c93c6d57a7).  I'd use (free) tools like http://www.cjwdev.co.uk/Software/ADTidy/Info.html or http://www.cjwdev.co.uk/Software/ADReportingTool/Info.html to get a handle on the domain, weeding out old/stale items and restoring order in the domain.  Just as importantly is building up some processes to avoid this from happening again, things like leavers/starters, naming conventions and structure. 

I'd also look at any related tasks that could be automated, the would go hand in hand with these sorts of operations. I'd throw in other infrastructure roles, like DHCP, DNS, printer servers etc, could they be refreshed alongside this work, or at a later stage.

For that actual upgrade, I'd look adding a 2012 R2 DC(s), https://blogs.technet.microsoft.com/canitpro/2015/02/10/step-by-step-migrating-windows-server-2003-fsmo-roles-to-windows-server-2012-r2/, decommission the 2003 ones. 2012 R2 can then be upgraded to 2016, or add a fresh 2016 DC.  Could be lots of other steps or permutations, worth researching and there are considerations like licencing as well.