BluSpring

Confirmed in 1.20.4

Potential Solution?
In StructureTemplate#placeEntities before Mob#finalizeSpawn, it might be possible to run some kind of structure placement validation check which corrects the positioning of the entity (and any future entities that may have a similar issue?) prior to finalization.

By converting the painting variant's width and height to block sizes (Variant#getWidth() / 16), if the height is even, offset the painting Y block pos down by 1. If the width is even, and the painting direction is west or south, offset by Direction#getClockwise().getNormal(), then set the painting pos to that position.

The mixin code I wrote to test this solution (in 1.20.2) looks like this: (MojMap)

@Mixin(StructureTemplate.class)
public class StructureTemplateMixin {
    // Injects into StructureTemplate#placeEntities, inside the lambda of createEntityIgnoreException
    @Inject(method = "method_17917", at = @At(value = "INVOKE", target = "Lnet/minecraft/world/entity/Entity;moveTo(DDDFF)V", shift = At.Shift.AFTER))
    private static void fixPaintingPlacement(Rotation rotation, Mirror mirror, Vec3 vec3, boolean bl, ServerLevelAccessor level, CompoundTag tag, Entity entity, CallbackInfo ci) {
        if (!(entity instanceof Painting painting)) {
            return;
        }

        var pos = new BlockPos.MutableBlockPos();
        pos.set(painting.getPos());
        var variant = painting.getVariant().value();

        var width = variant.getWidth() / 16;
        var height = variant.getHeight() / 16;
        var direction = painting.getDirection();

        // paintings with an even height seem to always be moved upwards...
        if (height % 2 == 0) {
            pos.move(0, -1, 0);
        }

        // paintings with an even width seem to be moved in the clockwise direction of their facing direction,
        // if they're west or south.
        if (width % 2 == 0 && (direction == Direction.WEST || direction == Direction.SOUTH)) {
            var moveTo = direction.getClockWise().getNormal();
            pos.move(moveTo);
        }

        painting.setPos(pos.getCenter());
    }
}