Default Location:
The app can ask the user to narrow down a default location, or this could perhaps be queried from the device being used. For example, in the absence of GPS or GEO IP I may have previously specified that I am in "Seattle, WA", or just "Washington", but maybe just "United States". This would allow you to zoom in onto a specific location.
This may not be where I currently am, but as it is my "home" it is more likely I am there and as good a place to initially zoom in on as any.
In the case of a mobile device, location services can be used - which can include cell tower or WiFi location estimations.
Ask the User:
If you can't tell where the user is. Ask them. You can do something similar to FedEx's splash screen.

This actually bugs the heck out of me because they always show this, even if I was at the site just 5 minutes ago! I wish they would at least use a GEO IP to guess where I am and then let me easily "zoom out" if necessary.
Show a Global Subset:
You can certainly show a global map view with a listing of locations around the world; but you can show a subset of those locations. For example: 1 location per "major" U.S. city, 2 locations for England, 3 for France, 5 for Russia, etc...
How do you determine what to highlight? Perhaps these sites have ratings; perhaps you just show a few random locations; perhaps it is just major cities; perhaps you make them pay you for the privilege.
In the example you show, also notice there are many smaller dots. You can include a "big dot" for what you are highlighting but show a few smaller dots for other locations.
Another option might be to show "bubbles" showing the number of locations in a certain location. The user can then drill down by clicking on the circle and zoom in on that region. You can have them do this a few times if you are in a region with lots of locations. For example: 100 stores in Washington State, click the circle to see more regions for Eastern WA, Puget Sound, Western WA, etc... Once you feel the list will not be too dense, you can show all the locations in that region.
