I would imagine that underlayment is the key to a good sidewalk, as it is for a good road. For years many New Hampshire roads seemed to be in much better shape than those in Mass. because of the deeper and multiple layers of underlayment before any asphalt was laid, which prevented frost heaves, cracking and a host of other issues. I would imagine the industrious Quebecois learned long ago to put down the right layers of underlayment before their paving stones.
Regarding brick for sidewalks: recall the sit-down demonstrations from the 1950's when the city of Boston threatened to tear up the "dangerous" brick sidewalks of Beacon Hill. The "Grandes Dames" of the Hill made quite a fuss and the brick was left in place. Brick was indeed used for sidewalks for centuries, though one might make the argument that it is being over-used now in the name of "place identity."