Your blumblumshub seems a good opportunity to try NestList:

Mod[Rest@NestList[Mod[#^2, 50515093] &, 290797, n], 500]

Removing AppendTo did speed it up! The following code completed in just under 6 minutes... thanks Frank!

ClearAll[blumblumshub, makelines, vectorXprod, euler165] 
blumblumshub[n_] := 
 Mod[Rest@NestList[Mod[#^2, 50515093] &, 290797, n], 500]
makelines[n_] := 
 Block[{raw = blumblumshub[4 n]}, 
  Map[{{raw[[#]], raw[[# + 1]]}, {raw[[# + 2]] - raw[[#]], 
      raw[[# + 3]] - raw[[# + 1]]}} &, Range[1, 4 n, 4]]]
vectorXprod[{a_, b_}, {c_, d_}] := a*d - b*c
euler165[n_] := 
 Block[{l = makelines[n], l1, l2, i, j, fl1, ll1, fl2mfl1, ll2, rxs, 
   t, u, hits = ConstantArray[0, 3000000], next = 1},
  For[i = 1, i < n, i++, l1 = l[[i]]; fl1 = First@l1; ll1 = Last@l1;
   For[j = i + 1, j <= n, j++, l2 = l[[j]]; fl2mfl1 = First@l2 - fl1; 
    ll2 = Last@l2;
    rxs = vectorXprod[ll1, ll2];
    If[rxs != 0, t = vectorXprod[fl2mfl1, ll2/rxs];
     If[t > 0 && t < 1, u = vectorXprod[fl2mfl1, ll1/rxs];
      If[u > 0 && u < 1, hits[[next++]] = fl1 + t*ll1]]]]];
  Length[DeleteDuplicates[hits]] - 1]
euler165[5000] // Timing