Solution File is too large to upload but pretty chuffed with cracking logic for this and my first approach bearing fruit. Basically made grids and found the nearest road to those grids and got more and more detailed. Before taking the centroid of grids.
That said its pretty brute force. In all a fun challenge
I'm using a first grid of 10 miles, then using the spatial match tool to identify every grid which are intersecting roads. After that, I see only on 10 mile square not intersecting roads, so I make a sub grid of 50 meters into this suqare, and using "find nearest" tool I can identify the farest point from the roads. My solution find ned at 24 meters (lon : -107.420774 | lat : 37.616304) in less than a minute (depending on computer performance of course) .