The trick with rim brakes is to get ones with replaceable blocks. In that way you can setup the brakes once so that they have perfect toe-in (small gap at back so they do not squeal) and so that they hit the rim dead-centre (not at an angle, falling off the bottom or hitting the tyre). Then, when the brakes get worn you can simply replace the inserts and not have to start again with the setup.
Due to different places selling different stuff and having made an investment in your setup, it then becomes a matter of what are the most widely available inserts. In the UK this probably means the 'Aztec' brand. From my personal experience the after-market Aztec blocks and shoes are better than the cheeze-o-blocks that Shimano supply. 'Kool Stop' are also pretty good and widely available in selected markets.
As for choice of rubber, if you are undecided, what is wrong with dual compound? In that way you get durability and stopping power all in one.
I am not wanting to specify a shop/endorse a brand, however, here is what you should be looking for (as Googled earlier).
You can always try the different compounds to see what works best front/rear, what wears your rims out quickest (soft on rear is a good idea as rear rims wear quicker) and what fits your budget.
Moving forward, the replacement shoes are a double whammy of time savings and money savings. Not only are they quicker to replace, they are cheaper and you do not lose your settings.
Enjoy your tour!