This is an interesting question, well suited to this site! The problem is a common one for touring cyclists wanting a 25-32mm tyre and mudguard, where the solution is to 'get a bike with cantilever bosses'. You have a compound problem of short reach, a measurement you could do with measuring.
The dual-pivot brake doesn't offer a lot of tyre clearance, but do you need dual pivot anyway? Campagnolo groupsets have the dual pivot on the front but single pivot on the back, here is the affodable-style Veloce option:
A high-end Campagnolo brake may just about work for you and be a classy addition to the bike, giving vastly improved stopping power over the Tektro efforts, but you still might struggle to get a big tyre on there.
You can mitigate against that by using a slightly thinner 16 * 1.35" Marathon Plus tyre - this will give you more puncture protection than the 16 * 1.75 Marathon and would be my preferred option. Note that the 16 * 1.35 Marathon will have a lower profile than the 16 * 1.35 Marathon Plus, so more room can be gained at the expense of puncture protection.
Also worth investigating are late 1980's era Weinmann and Dia-Compe side-pulls of the short-reach flavour. These will not have the stopping power of today's side-pulls, however, how much stopping power do you need to lock up the rear wheel? A bit of flex won't be the end of the world on the back brake, and these early brakes can be had for a good price. The shape of the arms on these brakes did allow for a reasonably fat tyre, the only real problem is getting the recessed allen key rather than bolt attachment. That said, the main bolt on the Weinmann brakes can be interchanged as they were available to suit recessed, Allen key fitting. Here are some Weinmann 500's, from centuries ago,but with compelling tyre clearance:
These were available in black. Another beauty is the 605. This one does not have the hex-bolt exposed to aid centering, but I don't think you can beat the combination of short reach and tyre clearance:
Ebay is going to be your friend here, another option you might want to investigate is center-pull. Sticking with Weinmann, here is the 999, seemingly available in short reach flavour:
You could run it U-brake style with some cable stop for the outer bolted onto the underside of the b/b, or investigate if that sort of thing is possible...