Finally got this working, had to use this formulation:
ObjectQuery<Dispatch> query = (from item in entities.Dispatches select item) as ObjectQuery<Dispatch>;
foreach (string s in includes)
query = query.Include(s);
var res = from d in query
where d.Route.Legs.Any(x =>
x.StartPoint.ArrivalTime >= start && x.StartPoint.ArrivalTime <= end ||
x.StartPoint.DepartureTime >= start && x.StartPoint.DepartureTime <= end ||
x.EndPoint.ArrivalTime >= start && x.EndPoint.ArrivalTime <= end ||
x.EndPoint.DepartureTime >= start && x.EndPoint.DepartureTime <= end)
select d;
Essentially, the main difference is that I'm doing an initial linq query, then attaching the includes and finally reselecting from that group with the where condition.