It strikes me that knowing that all streets run N_S or E_W will allow you to easily compute an excellent heuristic for the A* algorithm, which on first thought would seem to be the best general purpose algorithm to solve this.
With such a great heuristic you should be able to use an extremely sparse structure due to the ability to do extensive pruning.
EDIT - In response for the request to elaborate on the heuristic: With the A* algorithm one requires an admissible heuristic, {h(x)} that is an estimate of the distance from the current node to the target. To be "admissible" the heuristic, or estimate of the distance from the current point (x) to the goal must be less than or equal to the true distance. Normally one might use the straight line distance ("as the crow flies") between the two points, since no actual road could be shorter than a straight line.
In your problem you are told that all roads run north-south or east-west, thus no diagonal roads. Lets take a specific example: Suppose one wants to estimate the minimum distance, h(x), for starting at the point (0,0) and traveling to (10,10). Now this is a square with a side of length 10, so ordinarily one would estimate that there could be a road that went straight from (0,0) to (10,10) so the straight line distance would be the square root of 200 or approx 14.14. But in your case, since all roads run N-S or E-W we know that the minimum possible distance is 20. Of course the true distance might be more depending what roads are available.
Since you have an admissible heuristic for two points (x1,y1), (x2,y2) being h(x) = (abs(x2-x1) + abs(y2-y1)); this h(x) is always greater than or equal to the straight line distance, and thus is a "better" heuristic in that it will lead to a smaller solution space which will need to be explored. In other words greater tree pruning.