Narrow tread width, what the cool boys call the Q factor to baffle you, is an evil legacy from bike racing, where fractions of aerodynamic advantage are said to count. It doesn't have much to do with a touring bicycle or with a utility or commuting rider unless he is ultrafit and ultra-knowledgeable, the sort of person who has a special frame on his handlebars to hold a cheat sheet of which gears follow which in his derailleurs, which helps him achieve the maximum possible efficiency.
I have the same problem as you, that my stance is naturally wider then even a Rohloff chainlink (which the peloton boys have already pointed out to me is somehow "unnaturally" wide, whatever that means). Unfortunately, my favourite block pedals are the silky smooth VP-191 which are not very wide. I bought a pair of wiiiiide vintage block pedals on Ebay -- for which a collector acting via the seller instantly made me a higher offer -- but unfortunately I drove off the road on a lane where a harvester or tractor had knocked a piece out of the road and I was going too fast before dawn to see it, and snapped off one of these really super pedals as it caught the edge of the tarmac over the deep ditch. In several years I haven't been able to find another pair, which I imagine accounts for the other fellow's offer.
My solution is to use the pedals I like, the VP-191 (inexpensive as pedals go, stocked by SJS), and wear shoes with thick rubber soles which are naturally a little stiff, and simply not to pay attention to the fact that the pedals are not truly wide enough for my size twelves. I wouldn't advise this solution for a long distance tourer, because it might give him some kind of repetitive stress injury in the middle of his foot-soles, but for my day-rides I've never noticed an adverse reaction.
You might also with profit study the angle of cranks. Racing cranks and vintage cranks, and recreations of the latter by people like Orange in the States, are virtually perpendicular to the ground, in aid of that narrow tread everyone in cycling axiomatically assumes is a good thing. However, angled cranks are available, and they can give you valuable centimetres of outward spacing. Instead of trying to make up all the extra pedal separation you need all in one bound with a longer bottom bracket and pedal shaft extenders, I would suggest that it is more sensible to divide the distance by as many means as available: longer axle in your bottom bracket, bottom bracket spacers, angled cranks, pedal axle extenders. Furthermore, don't try for too much at once: do it in steps, with adequate time on the bike to get used to one adjustment before you make the next. My own experience is that millimetres make a difference to a satisfactory bike fit, so that it is a pleasure to ride the bike rather than a duty; the obverse is that the same millimetres can make you so acutely uncomfortable that you mistakenly start to believe you need a huge adjustment.
About you on your bike feeling like a gorilla in too small a cage, perhaps I missed the part where you say you raised the seat post and then moved it horizontally until you are in a comfortable position, after which you may also have to adjust the handlebars because with your back at your preferred angle, your reach to the handlebars will have changed. Fiddly, but you have to do it only once.
All these adjustments interact, another reason to proceed by small steps.
