@Matma Rex
I'm not sure if finding the point farthest from the edge (essentially, the centre of the inscribed circle) is computationally hard or not. However, finding the bounding box is easy enough, finding its centre is trivial, determining whether that centre is at least some specified distance away from any point of the edge is relatively easy as well. Sure, that won't give you all centre points, but it will give you many of them. Sure, they won't be "perfect", but they'll be good enough.
The way I see it, you shouldn't try to solve it fully automatically; that's way too hard (it would only make sense if you're gonna make many dozens or hundreds of maps, automatically). Instead, you should aim at doing most of the grunt work automatically (which keeps the effort to create the automation in the first place manageable), than solve the corner cases manually.

For a possible solution to the "different scales" (having a map with both the, generally small, European countries and the Americas, Australia and Russia) you could take a look at the "Canada Big" map. Of course that's not something which can be done automatically, but if you could create a manually-preprocessed SVG and feed *that* to the script.