Navigating through entries within a category when they belong to multiple
I think you are on the right track, in that you will likely need to create a separate route for the entries when they are 'featured', so that you can configure the nav properly in the template. I can think of a few ways to do this (and I'm sure there are more).



Add a custom route, adding a '/featured/' segment to the uri. Then in the entries template test for the segment, and modify the entries ('params') and the nav accordingly.

{% set isFeatured = (craft.request.getSegment(2) == 'featured') ? true : false %}
{% if isFeatured %}
    {% set params = craft.entries.section('galleries').relatedTo(categories.featured) %}
    {% nextUrl = siteUrl ~ '/featured/' ~ entry.getNext(params).slug %}
    {% prevUrl = siteUrl ~ '/featured/' ~ entry.getPrev(params).slug %}
{% else %}
    {% set params = craft.entries.section('galleries').relatedTo(categories.galleries) %}
    {% nextUrl = entry.getNext(params).url %}
    {% prevUrl = entry.getPrev(params).url %}
{% endif %}




Add a parameter to the uri (i.e. ?v=featured and test for the parameter in the template. Then pass the parameter on in the navigation.

{% set isFeatured = (craft.request.getParam('v') == 'featured') ? true : false %}
{% if isFeatured %}
    {% set params = craft.entries.section('galleries').relatedTo(categories.featured) %}
    {% nextUrl = entry.getNext(params).url ~ '?v=featured' %}
    {% prevUrl = entry.getPrev(params).url ~ '?v=featured' %}
{% else %}
    {% set params = craft.entries.section('galleries').relatedTo(categories.galleries) %}
    {% nextUrl = entry.getNext(params).url %}
    {% prevUrl = entry.getNext(params).url %}
{% endif %}




Abstract the relationship by creating a new 'featured' entries channel, with an entries field that links to the actual entry. Then the 'featured' category can link to the 'featured' entries (which are subsequently linked to the real entries). The featured template can then just include the normal entry with a variable isFeatured=true or something.

// In 'featured' entry template
{% include 'mychannel/_entry' with { entry: entry.myEntriesField, isFeatured: true } only %}

// In native entries template
{% if isFeatured %}
    {% set params = craft.entries.section('galleries').relatedTo(categories.featured) %}
{% else %}
    {% set params = craft.entries.section('galleries').relatedTo(categories.galleries) %}
{% endif %}




I'm sure there are more but one those might work.