Looking for an efficient algorithm quickly find the nearest line (defined by perpendicular distance) to an arbitrary point
All your lines define a planar subdivision, where each polygonal region is bounded by a finite number of line segments or rays. So, at first you need to find a (probably infinite) region, containing a query point, and then you'll be able to select its boundary line with minimum distance from this point.

There are many ways to preprocess a planar subdivision in order to solve the Point location problem with logarithmic time complexity. Some hierarchical data structure is typically devised, which can be traversed for any query point, and it's proved, that the length of the traverse path is limited by $O(log(N))$, where $N$ is the number of regions. As @Pseudonym mentioned in comments, you can also use Binary space partitioning (BSP) to build a BSP tree - it's also a hierarchical data structure (binary tree), which will allow you to efficiently find a region, containing a query point. It looks like your problem suits well for this BSP approach. 

Sorry to say, you can get regions with $O(n)$ boundary segments/rays, where $n$ is the number of lines. To overcome this difficulty you can further subdivide each region into Voronoi diagram, generalized for its boundary segments and rays. It's easy to see that the total number of such refined regions will be limited by $O(n^2)$, which still gives you logarithmic time complexity for the nearest line search. However in average case these regions with many boundary segments/rays will make up a small fraction of all regions - so in average you still will be able to quickly select the closest boundary segment/ray just by looping over the region boundary. 



If you want to know more about general properties of the geometric structure you're working with - it makes sense to read this Wiki page.