Ordering entries based on an eager-loaded element's custom field
This requires a bit of extra work on the ElementQuery, but it can be done in the same query.

We need to perform an inner join on the relation between the movie and the show and then another inner join on the show's content table. Finally we can order on the custom field of the show's content table.

{% set currentMovies = craft.entries()
    .section('movies')
    .type('movie')
    .limit(null)
    .with([
        'shows',
        'poster',
        'stills'
    ])
    .innerJoin('{{%relations}} shows_relation', '[[shows_relation.sourceId]] = [[elements.id]]')
    .innerJoin('{{%content}} shows_content', '[[shows_content.elementId]] = [[shows_relation.targetId]]')
    .orderBy('shows_content.field_startingDate asc')
%}