holy crap, that was a close one:
Spain, Paragon/Normal, Victory: 1700AD, Scenario: 600AD, SVN 862, Score: 25081
UHV 1 & 2 are rather easily accomplished but UHV 3 is a tough one (the 40% part, not the other one).
You'll have Protestantism spread to ~33% of your cities even if you join the counter-reformation and the rest of Europe will probably have even worse numbers, unless you get lucky. So try to get the reformation-event as soon as possible.
Problems I had in my game:
China never collapsed, the Ottomans got huge, Vikings & HRE got Protestantism in every city they had.
Approach: (Yeah this is the one with extra-cheese)
1. Settle Madrid & Santiago, Madrid builds a Settler, Santiago a galley, research guilds
2. Switch to Slavery&Theocracy, use your Knights and troops to raze Bordeaux and ideally Marseilles (I did this in 750AD, which denied France a settler, so they founded a city in the North-West and France only.
3. Get Barcelona before the Moors do, build a 2nd settler in Madrid.
4. At the same time: load your first settler onto the galley and set sail for England, found Murcia on the Iron the turn after they flip that area. (this denies them Iron, meaning they won't have Knights/Pikemen later)
5. Build a galley or two in Barcelona, build some Cats and ship your troops to take Alexandria (sue for peace afterwards, unless you can also take Cairo), your 2nd settler founds Pamplona, 2N of Madrid (can use the crabs+wine and is an early 3rd city in your core)
After this your next goals are:
- Rome
- France, Cordoba once you have guilds, England soon after (remember: they only have Longbowmen and Horse Archers), Portugal (raze it!) whenever convenient.
Your only competition for the conquerer-event should be the Norse, so you'll probably have enough time to research Astro before going for it (steal Gunpowder from the Ottomans)
I made the mistake of not researching Divine Right on my own (bought it from Mali) but this means you won't be able to get other civs to adopt Fanaticism as easily.
Try to get open borders with Japan & Russia.
Once you have Astro, Barcelona & Cordoba become part of your core, easing all expansion problems. Incas & Aztecs usually collapse in the 1600s if you vasallize them.
For the gold: settle California early, go for Sydney & South Africa if needed (but there is quite a lot in the Americas)
For the no Protestant civs:
Join the counter-reformation (obviously), I usually found Protestantism myself to have it earlier in the game, prosecute as quickly as you can. Usually either the Vikings or the HRE will convert, your Conquistadores and a few Bombards will destroy them.
The Dutch can be convinced to become fanatic Catholics (send a missionary to them, spread it, bribe them to switch to Catholicism, use a spy to get them to adopt Fana) or you fight them.
For the 40%:
Since Prosecution is the only way of removing a religion for you and you can only do it in one town at a time, the best way is to ignore the Protestantism in Europe (except in your big cities, of course) and go for non-believers like the Ottomans or Chinese (Japanese are probably a great target now that I think of it), raze and starve them