Shift backend-specific code for supporting extension modules to those modules?

It is indeed a very complex problem and I appreciate that you have put some thought into it. I think that it should always be possible for a new module that wants to implement a new feature to control the whole flow and not be dependent on the maintainer of the backend to implement the feature for the certain backend.
Also, I'm not sure in which matter we need a backend to support all possible extensions. A backend should at least support the base Search API, with as many features as the backend claims to support using the getSupportedFeatures() and perhaps with a minimum of a couple enforced features such as basic search and filters?

An extension module could then alter each separate feature of a specific backend, as you mentioned or add a specific feature. In Drupal 7 this would be something like

function search_api_location_search_api_feature() {
  return array(
     'search_api_solr' => array(
       'feature' => 'search_api_location'
       'query callback' => 'search_api_location_query'
     ),
    'search_api_db' => array(
       'feature' => 'search_api_location'
       'query callback' => 'search_api_location_solr_query'
     ),
  );
}

And the alter could happen in the same way. If we make each feature a class? of its own, it would even be easier for the alteration, custom or contrib to subclass it and then alter or add to the feature definition list. We did similar things for the Apache Solr module to support arbitrary entities, a register with callbacks for each entity, and if the array of callbacks was present, the UI showed a checkbox that enabled that "feature" to index that specific entity.

For example, search_api_location is then responsible for choosing which backends it supports and which features it supports. The hook that adds the feature can decide which backends it adds the support for and where the implementation lives.

I'm not entirely sure how this thinking maps to Drupal 8 but I'm sure we're not the only ones with this architecture issue.

Oh and also, in the query of the backend, I think it should take the Query object and all other possible parameters and pass it to those implementation callbacks for each feature the query is trying to accommodate to. Since we are passing objects to all the callbacks it should be possible to add query details.

The ordering might be tricky as some query implementations depend on other features. So perhaps we need a dependency chain where a feature depends on other features. Eg, location depends on the filters to already be there so the example would be:

function search_api_location_search_api_feature() {
  return array(
     'search_api_solr' => array(
       'feature' => 'location'
       'query callback' => 'search_api_location_query',
      'dependencies' => array('filters'),
     ),
    'search_api_db' => array(
       'feature' => 'location'
       'query callback' => 'search_api_location_solr_query',
       'dependencies' => array('filters'),
     ),
  );
}

We should get a review from @mkalkbrenner as well if possible, but I feel this is a good improvement.

The patch looks good and I'm basically fine with that API change. But in real life I see a lot of problems with this approach for more sophisticated extensions:

1. The maintainer of an extension could not be familiar with all backends. At the moment we have three "first class" backends, DB, Solr, Solr Multilingual. But there is Elastic Search and others. Therefor other maintainers input will be required nevertheless. And then I prefer to maintain the code within the backend as to be forced to provide patches for extension modules.
2. Some of these extensions might require Solr schema adjustments, for example geo location. There's no API for that and it is not supported by most Solr service providers.

Therefor I'm not completely sure, if that patch should be committed or not.

ok, convinced