El Editor puede crear cualquier nuevo usuario excepto administrador

En realidad es bastante sencillo. Necesitas filtrar en map_meta_caps para evitar que los editores creen/editen administradores, y eliminar el rol de administrador del array de 'editable roles'. Esta clase, como plugin o en el archivo functions.php de tu tema, lo haría:

class JPB_User_Caps {

  // Añadir nuestros filtros
  function __construct(){
    add_filter( 'editable_roles', array($this, 'editable_roles'));
    add_filter( 'map_meta_cap', array($this, 'map_meta_cap'), 10, 4);
  }

  // Eliminar 'Administrador' de la lista de roles si el usuario actual no es admin
  function editable_roles( $roles ){
    if( isset( $roles['administrator'] ) && !current_user_can('administrator') ){
      unset( $roles['administrator']);
    }
    return $roles;
  }

  // Si alguien intenta editar o eliminar un admin y ese usuario no es admin, no permitirlo
  function map_meta_cap( $caps, $cap, $user_id, $args ){

    switch( $cap ){
        case 'edit_user':
        case 'remove_user':
        case 'promote_user':
            if( isset($args[0]) && $args[0] == $user_id )
                break;
            elseif( !isset($args[0]) )
                $caps[] = 'do_not_allow';
            $other = new WP_User( absint($args[0]) );
            if( $other->has_cap( 'administrator' ) ){
                if(!current_user_can('administrator')){
                    $caps[] = 'do_not_allow';
                }
            }
            break;
        case 'delete_user':
        case 'delete_users':
            if( !isset($args[0]) )
                break;
            $other = new WP_User( absint($args[0]) );
            if( $other->has_cap( 'administrator' ) ){
                if(!current_user_can('administrator')){
                    $caps[] = 'do_not_allow';
                }
            }
            break;
        default:
            break;
    }
    return $caps;
  }

}

$jpb_user_caps = new JPB_User_Caps();

EDITADO

Ok, he investigado por qué permitía la eliminación de usuarios. Parece que delete_user se maneja ligeramente diferente a edit_user; he modificado el método map_meta_cap para solucionarlo. Lo he probado en 3.0.3 y esto evitará que cualquier persona que no sea administrador pueda eliminar, editar o crear un administrador.

EDITADO 2

He actualizado el código para reflejar la respuesta de @bugnumber9 más abajo. ¡Por favor, vota positivamente esa respuesta!

A pesar de tener aproximadamente 7 años, este hilo se puede encontrar fácilmente en Google y aún proporciona una solución funcional. Me refiero al código proporcionado por @John P Bloch.

Dicho esto, bajo PHP 7 produce un error no crítico (PHP Deprecated) como sigue:

PHP Deprecated: Methods with the same name as their class will not be constructors in a future version of PHP; JPB_User_Caps has a deprecated constructor in ...

Para solucionar esto, simplemente reemplaza este fragmento:

// Añadir nuestros filtros
  function JPB_User_Caps(){
    add_filter( 'editable_roles', array(&$this, 'editable_roles'));
    add_filter( 'map_meta_cap', array(&$this, 'map_meta_cap'),10,4);
  }

con este:

// Añadir nuestros filtros
  function __construct() {
    add_filter( 'editable_roles', array(&$this, 'editable_roles') );
    add_filter( 'map_meta_cap', array(&$this, 'map_meta_cap'), 10, 4 );
  }

Esto solucionará el problema.

Estaba buscando una solución donde el Editor pudiera editar solo los menús Y crear/editar usuarios sin necesidad de un plugin. Así que terminé haciéndolo para aquellos que estén interesados.

// Personaliza el rol 'Editor' para tener la capacidad de modificar menús, agregar nuevos usuarios
// y más.
class Custom_Admin {
    // Añade nuestros filtros
    public function __construct(){
        // Permite al editor editar opciones del tema (ej. Menú)
        add_action('init', array($this, 'init'));
        add_filter('editable_roles', array($this, 'editable_roles'));
        add_filter('map_meta_cap', array($this, 'map_meta_cap'), 10, 4);
    }

    public function init() {
        if ($this->is_client_admin()) {
            // Deshabilita el acceso a las páginas de temas/widgets si no es admin
            add_action('admin_head', array($this, 'modify_menus'));
            add_action('load-themes.php', array($this, 'wp_die'));
            add_action('load-widgets.php', array($this, 'wp_die'));
            add_action('load-customize.php', array($this, 'wp_die'));

            add_filter('user_has_cap', array($this, 'user_has_cap'));
        }
    }

    public function wp_die() {
        _default_wp_die_handler(__('No tienes permisos suficientes para acceder a esta página.'));
    }

    public function modify_menus() 
    {
        remove_submenu_page( 'themes.php', 'themes.php' ); // oculta el submenú de selección de temas
        remove_submenu_page( 'themes.php', 'widgets.php' ); // oculta el submenú de widgets

        // Menú Apariencia
        global $menu;
        global $submenu;
        if (isset($menu[60][0])) {
            $menu[60][0] = "Menús"; // Renombra Apariencia a Menús
        }
        unset($submenu['themes.php'][6]); // Personalizar
    }

    // Elimina 'Administrador' de la lista de roles si el usuario actual no es un admin
    public function editable_roles( $roles ){
        if( isset( $roles['administrator'] ) && !current_user_can('administrator') ){
            unset( $roles['administrator']);
        }
        return $roles;
    }

    public function user_has_cap( $caps ){
        $caps['list_users'] = true;
        $caps['create_users'] = true;

        $caps['edit_users'] = true;
        $caps['promote_users'] = true;

        $caps['delete_users'] = true;
        $caps['remove_users'] = true;

        $caps['edit_theme_options'] = true;
        return $caps;
    }

    // Si alguien intenta editar o eliminar un admin y ese usuario no es admin, no lo permitas
    public function map_meta_cap( $caps, $cap, $user_id, $args ){
        // $args[0] == other_user_id
        foreach($caps as $key => $capability)
        {
            switch ($cap)
            {
                case 'edit_user':
                case 'remove_user':
                case 'promote_user':
                    if(isset($args[0]) && $args[0] == $user_id) {
                        break;
                    }
                    else if(!isset($args[0])) {
                        $caps[] = 'do_not_allow';
                    }
                    // No permitas que un no-admin edite a un admin
                    $other = new WP_User( absint($args[0]) );
                    if( $other->has_cap( 'administrator' ) ){
                        if(!current_user_can('administrator')){
                            $caps[] = 'do_not_allow';
                        }
                    }
                    break;
                case 'delete_user':
                case 'delete_users':
                    if( !isset($args[0])) {
                        break;
                    }
                    // No permitas que un no-admin elimine a un admin
                    $other = new WP_User(absint($args[0]));
                    if( $other->has_cap( 'administrator' ) ){
                        if(!current_user_can('administrator')){
                            $caps[] = 'do_not_allow';
                        }
                    }
                    break;
                break;
            }
        }
        return $caps;
    }

    // Si el usuario actual se llama admin o administrativo y es un editor
    protected function is_client_admin() {
        $current_user = wp_get_current_user();
        $is_editor = isset($current_user->caps['editor']) ? $current_user->caps['editor'] : false;
        return ($is_editor);
    }
}
new Custom_Admin();

La solución de @John P Bloch sigue funcionando bien, pero pensé en compartir también mi pequeño filtro para 'map_meta_cap'. Un poco más corto y limpio, al menos para mis ojos ;)

function my_map_meta_cap( $caps, $cap, $user_id, $args ) {
  $check_caps = [
    'edit_user',
    'remove_user',
    'promote_user',
    'delete_user',
    'delete_users'
  ];
  if( !in_array( $cap, $check_caps ) || current_user_can('administrator') ) {
    return $caps;
  }
  $other = get_user_by( 'id', $args[0] ?? false ); // Comprobación en PHP 7 para variable en $args...
  if( $other && $other->has_cap('administrator') ) {
    $caps[] = 'do_not_allow';
  }
  return $caps;
}
add_filter('map_meta_cap', 'my_map_meta_cap', 10, 4 );