Here is a meta-answer, without going into detail on the underlying optimization problems.
From the title of your question, and from your description, it sounds like you have two different problems:
Start with a sphere subdivided into rectilinear regions in spherical coordinates, for arguments sake, let's say each region is closed, and an arbitrary point A.
Problem #1. Determine which region(s) contains point A. The point A can only be contained in more than one region if it lies on the boundary of each region. Let's assume you have already solved this one.
Problem #2. Given an arbitrary region R, determine B, the closest point of R to A (in spherical distance or Euclidean distance, doesn't matter which).
Solution: Two cases: Case (1) A is in R, in which case B=A. Case (2) A is not in R, in which case B lies on the boundary of R. The boundary of R in general [2.0] consists of 4 arcs: two meridians of longitude, which are arcs of great circles and two parallels of latitude, which are arcs of small circles. There are also special and degenerate subcases: [2.1] R is a sector of a north or south polar cap, in which case the boundary consists only of 3 arcs: two meridians meeting in a pole, and one parallel; [2.2] R is a whole polar cap, with only one parallel as a boundary; [2.3] R is the difference between two caps, with a boundary consisting of two parallels; [2.4] R is a sector of the whole sphere from one pole to the other, with two meridians as a boundary; [2.5] R is a hemisphere with both poles on the boundary, where the two meridians degenerate into a single great circle; [2.6] R is the whole sphere - this is excluded anyway, since in this case, A lies in R.
In the subcase [2.0], B may lie on any of the 4 arcs or on the 4 vertices which are the intersections of pairs of arcs. In any case, the small circle with centre A and radius AB either intersects R only at B, in which case B is unique, or all along one of the arcs, or at two vertices, in which cases B is not unique.
Intersection along all of a parallel arc occurs only when A is one of the poles. Intersection along all of a meridian arc occurs only when A is on the equator at a longitude 90 degrees away from the meridian arc. Intersection at two vertices can occur when the longitude of A is halfway between the two meridian arcs (or 180 degrees away from halfway in between, far enough away that the radius AB is greater than the radius of the smaller of the two radii of the parallel arcs, but close enough that the larger radius parallel arc is not closer to A than the smaller radius arc.
As per the other answers, you can treat [2.0] as 4 constrained optimization problems: find the closest point to A on each of the arcs. Once you have all 4 solutions, pick the closest one.
(Still in [2.0]) To get a (very rough) approximation, let's assume you can easily find the "centre" C of the region R in spherical coordinates. Now try to find the intersection (if any) between the arc AC and each of the boundary arcs of R. This will result in a point D which is either on one of the boundary arcs, or is one of the 4 vertices.