Postgres Proper Index for Sorting and Join
The reason for the poor performance is that the barcodes occurring earlier in the alphabet have been preferentially depleted from the location table.

It is easy to reproduce this with your random data seeds by just populating locations with twice as many records, and then deleting the "first" half of them:

INSERT INTO locations (id, barcode_id) SELECT seed.id, (RANDOM() * 500000)
    FROM generate_series(1,120000) AS seed(id);

DELETE from locations c where id in (
    select d.id from locations d
        JOIN barcodes ON d.barcode_id = barcodes.id 
        ORDER BY barcodes.value ASC limit 60000
);


There is not much hope for getting PostgreSQL to understand this weird cross-table relationship.

You might be able to get somewhat better performance by doing something like

set local enable_nestloop TO off;


But the real solution is probably to rethink how you are organize your data, or what you are trying to do with it.  Usually barcodes serve as their own primary keys.  Why do you need a separate table just to map a barcode to a primary key?  And why do you need to know the lowest barcodes which exist somewhere (anywhere) on a regular basis?  It sounds like an X-Y problem.