Longest-path in a graph, where the path should be 'straight'
Idea 1: Short paths are straight paths

In Euclidean space, a straight path is usually a short path.

So I would compute shortest paths between every pair of points in the graph.  This can be done in $O(|V|^3)$ time with the Floyd-Warshall algorithm, which is suitable for dense graphs, or $O((|E|+|V|)|V|\log|V|)$ time by running Dijkstra's algorithm starting from each vertex in turn, which is faster for sparse graphs.

You can then evaluate each vertex pair according to whatever "straightness" criteria you like -- e.g. average/maximum angle formed or maximum perpendicular distance, balancing these against the length of the path somehow -- and choose the overall maximum.

For a quick heuristic, you could randomly subsample the points and solve the smaller subproblem.  Repeat this several times to build a list of candidate (source, sink) pairs, then run Dijkstra on each candidate in the full graph to pick the overall winner.

Idea 2: Partition edges by angle

The above should work well if it's OK for the line to be quite jagged at a small scale.  But if smoothness at a small scale is important, another approach comes to mind: Partition the edges into angle buckets (e.g. all edges making an angle of 0-5 degrees with the horizontal, all edges making an angle of 6-10 degrees, etc., for 360/5 = 72 buckets overall).  For each bucket, solve a separate subproblem that contains all vertices, but only the edges in that particular bucket.  Every path in such a graph necessarily contains only edges that have very similar directions.  (If you choose sufficiently fine buckets, you might find that the graph fragments into many small, line-like components, which will speed things up greatly as they can be solved independently.)

In fact it's not necessary to partition the edges; it's probably desirable to have some bucket overlap, so that an edge typically appears in more than one subproblem.