For anyone who comes here in the future with a similar problem ...

As mentioned before, adding indexes made little difference on it's own, with the query as it stood.

However, I then changed my query to use apoc.coll.different() and apoc.coll.max() and this made a huge difference.