Currently the only way I know of to get an AI race to show you where their Civ is located, is to open an Exploration Treaty. Unfortunately that requires relations to be a +2 or better, and of course Navigators can't do treaties. It would be nice if they added an option under the "I have something else in mind" dialog tree like "I would like to send a trade ship to your Capital, would you reveal its location for 500 credits?".
There is a "one per Galaxy" improvement called "Eyes of the Universe" (at least I think it's still in the game), that shows every Civs Capital's location. Usually the AI beats me to it.
The only other way to see distant sectors is to use flag ships to survey artifacts and find a "Distant Vision". Obviously this is pure luck of the draw and they're too rare to use just pointing at vacant space. The odds of finding something would be way too low since the area they reveal isn't that large.
Maybe someone else knows something I've missed.