You could try adding "AND l2.start > l1.start" to the first query. This will drop symmetric half of intersections (the ones that will remain are l2 inside or to the left of l1), but you can redo results by id1,id2 union all id2, id1 and may allow to use start index for "between", for my "like" test this looks like the next:
" -> Index Scan using location__start on location l2 (cost=0.00..756.34 rows=37787 width=12)" " Index Cond: ((l2.start < l1.eend) AND (l2.start > l1.start))"
also an index on (objectid, start) would help resulting in :
" -> Index Scan using lt on location l2 (cost=0.00..0.84 rows=20 width=16)" " Index Cond: ((l2.objectid = l1.objectid) AND (l2.start < l1.eend) AND (l2.start > l1.start))"
