I have never used Marathons (I'm sure they're very good) but I would put a vote in for Michelin City tyres. Quite cheap, easily the most durable tyre I've come across so far, 2,000 miles, no punctures and they look the same as the day I put them on with no obvious tread wear or any sign of little cuts and bits of damage you sometimes see.
The only thing to be wary of it that they are over-sized. Mine are supposedly 27 x 1 1/4" but look more like 37 rather than 32 and this could cause problems on tight fitting frames.