How to set minimum required size for featured image?

The best solution I can come up with is a two-parter which adds metadata, then filters the images users are allowed to select from.

If I find a way to update the selector to add an alert, I’ll add that as a separate answer.

1st: Add image metadata that will allow us to filter images later

add_filter('wp_generate_attachment_metadata', 'wpse_add_meta', 10, 2);
function wpse_add_meta($meta, $id){
    if (array_key_exists('height',$meta)){
        update_post_meta($id, 'height', (int) $meta['height']);
        update_post_meta($id, 'width', (int) $meta['width']);
    }
    return $meta;
}

2d: Filter images returned by the Featured Image selector, using the new meta values for Height and Width (added in filter above).

add_filter('ajax_query_attachments_args', 'e2_attachments_ajax' );
function e2_attachments_ajax($query){
    $minHeight = 400;
    $minWidth = 758;
    $query['meta_query'] = array(
        'relation' => 'AND',
        array(
            'key'     => 'height',
            'value'   => $minHeight,
            'type'    => 'numeric',
            'compare' => '>',
        ),
        array(
            'key'     => 'width',
            'value'   => $minWidth,
            'type'    => 'numeric',
            'compare' => '>',
        )
    );

    return $query;
}

NOTE: For existing sites, you will want to run a process to update existing uploaded images. Run this after the you have added the first filter, “wp_generate_attachment_metadata” so it will update the height and width attributes. I recommend something like Ajax Rebuild Thumbnails.