The missing piece of the puzzle was the Umbraco HeadlessConfiguration.

Instead of creating services like this

public MyService : IMyService {
     private readonly PublishedContentService publishedContentService;
     private readonly MediaService mediaService;

    public MyService(PublishedContentService publishService, MediaService mediaService)
    {
        this.publishedContentService = publishedContentService;
        this.mediaService = mediaService;
    }
}

Pass over the IHeadlessConfiguration, the settings are in appsettings.json. It's called ImageBaseUrl.

Add the following to Startup.cs

services.AddSingleton<IHeadlessConfiguration, HeadlessConfiguration>();

Then change the service layer to:

public MyService : IMyService {
     private readonly PublishedContentService publishedContentService;
     private readonly MediaService mediaService;
     private readonly IHeadlessConfiguration configuration;          

    public MyService(IHeadlessConfiguration config)
    {
        this.publishedContentService = new PublishedContentService(config);
        this.mediaService = new MediaService (config);
        this.configuration = config;
    }
}

When accessing the media, the url will still be relative, but now we have the base url, so we can build the url ourselves.

public async Task<Location> GetLocationByIdAsync(int locationId)
    {
        var query = Query.Where.Property(nameof(Location.locationId)).EqualTo(locationId);
        var location = (await publishedContentService.Query<Location>(query)).FirstOrDefault();
        if(location != null ) 
        {
            location.ImageUrls = location.PromoImages.Select(x => $"{configuration.ImageBaseUrl}{x.Url}");
        }

        return location;
    }