Gold is the easiest and is the best choice as said. However even with a successful steal you can be spotted and caught or killed which is not made that clear. So even using a +2 skill does not help as much as a spy level in surviving and being promoted.
I will try and get the intelligence agency before using spies as I believe that gives a level to all spies. I'll do this from now on - thanks
I will also always take quartermaster as first spy if I can, not so much for defence (which is fine) but because it also gives a level to spies. Cryptography also is great. Naturally having Cathering also helps.
So a key rule is do not go spying as a level1 spy because you are rather likely to die, even stealing gold. There will be those that disagree because we do not have the precise formula but I have some pretty good idea of how it works now and being the highest level while escaping is key to surviving which is what you are asking, it also helps with your tasks.
I personally prefer to take ace driver as one of my first promotions after my quartermaster is assigned at home. 4 levels on escape is quite OP, also I believe enemy spy levels count against you if they are in the city.
Machiavellianism is really key to slot, not for the discount build but for the time reduction. Spy mission feel like they take a long time and adding escape times to relocation and mission times really makes each task quite long.
So feel free to go for gold mission first but do not spend a lot of time doing this because it does take valuable time. If your first spy can go out with 2 additional levels you may want to go directly for a riskier but much more valuable task like killing envoys. Your levels for escape really do buff you a lot amd people seem to get fixated on the steal strength rather than the survivability strength which you seem to be grasping. Another great promotion is reducing your mission time by another 25%... all these +2 attack values are great but to what end? More gold? You already have loads... the +2 gold promotion is not really worth it, once you have a extra level you are that much tougher.
So I will want quartermaster before I go offensive personally. If my first spy cannot have it I will give them something else and use them as an extra level of intelligence for combat purposes until I can get quartermaster... or at least intelligence agency. Playing as Catherine is quite OP when combined with the above.