Efficient algorithm for finding pairs of nearby, parallel streets in a map
Your idea of processing the segments in bins is not bad. You do need to think through what happens to road segments that traverse bin boundaries.
Another idea is to Hough transform all the road segments. The infinite line that each segment lies on corresponds to a point in 2d Hough space: the polar angle of the line is one axis and the distance to the origin of the line's nearest point is the other.  The transformation from two points on a line to a Hough point is simple algebra. 
Now you can detect nearly co-linear road segments by using a closest point pair algorithm. Happily this can be done in O(n log n) expected time. E.g. using a k-d tree. Insert all the points in the tree. Use the standard k-d tree algorithm to find each point's nearest neighbor. Sort the pair distances and take a prefix of the result as pairs to consider, stopping where the pairs are too far apart to meet your criterion of "nearby and parallel".  There are O(n) of such nearest neighbor pairs.
All that's left is to filter out segment pairs that - though nearly co-linear - don't overlap. These segments lie on or near different parts of the same infinite line, but they're not of interest. This is just a little more algebra.
There are reasonably good Wikipedia articles on all of the algorithms mentioned here. Look them up if they're not familiar.
I am working on a Python program that processes map data from Openstreetmap, and I need to be able to identify pairs of streets (ways) that are close to each other and parallel. Right now, the basic algorithm I'm using is quite inefficient:

Put all of the streets (Street objects) into a large list
Find every possible pair of two streets in the list using nested for loops; for each pair, draw a rectangle around the two streets and calculate the angle at which each street is oriented.
If the rectangles overlap, the overlapping area is big enough, and the angles are similar, the two streets in the pair are considered parallel and close to each other.

This works well for small maps but with large maps, the biggest problem obviously is that there would be a huge number of pairs to iterate through since there could be thousands of streets in a city. I want to be able to run the program on a large area (like a city) without having to split the area into smaller pieces.
One idea I'm thinking of is sorting the list of streets by latitude or longitude, and only comparing pairs of streets that are within, say, 50 positions away from each other in the list. It would probably be more efficient but it still doesn't seem very elegant; is there any better way?
Each Street is composed of Node objects, and I can easily retrieve both the Node objects and the lat/long position of each Node. I can also easily retrieve the angle at which a street is oriented.