Automatically remove Gutenberg Blocks text format during uninstall

Could try adding a hook_uninstall to gutenberg/gutenberg.install

Please try adding this hook_uninstall to your gutenberg.install file and then rebuild cache, uninstall the module and see if this works.

/**
 * Implements hook_uninstall().
 */
function gutenberg_uninstall() {
  // Remove the filter from all text formats.
  $config_factory = \Drupal::configFactory();
  $text_formats = \Drupal\filter\Entity\FilterFormat::loadMultiple();

  foreach ($text_formats as $format) {
    $config = $config_factory->getEditable('filter.format.' . $format->id());
    $filters = $config->get('filters');

    if (isset($filters['gutenberg'])) {
      unset($filters['gutenberg']);
      $config->set('filters', $filters)->save();
    }
  }
}

We already have something similar at the hook_uninstall. The issue is that Gutenberg can't be uninstalled while its filter plugin is being used in the Gutenberg text format.
Not sure if Drupal has some kind of "force" mechanism for uninstalling modules.
Another solution would be try to add a button at the uninstall page to remove that text format.