How to display place names for a map?

[guyanonymous]

I'm trying to decide how best to display the names of countries and capitals on my map.

Being a world map with lots of locales, it would be both a tight fit and unreadable at less than full resolution if I labeled things directly on the map.

I'm thinking of orienting things like so:

_________________________________
| ______________________________ |
| |                            | |
| |                            | |
| |                            | |
| |         map itself         | |
| |         (w coord)          | |
| |                            | |
| |                            | |
| |                            | |
| |____________________________| |
|                                |
|  xxxxxxxx xxxxxxxxx  xxxxxxxx  |
|  xxxxxxxx xxxxxxxxx  xxxxxxxx  |
|  xxxxxxxx xxxxxxxxx  xxxxxxxx  |
|  xxxxxxxx xxxxxxxxx  xxxxxxxx  |
|  xxxxxxxx xxxxxxxxx  xxxxxxxx  |
|  xxxxxxxx xxxxxxxxx  xxxxxxxx  |
|________________________________|

Where xxxxxxxx is something like "a-b City of Country" (a-b is the coordinates).

Any thoughts? Alternate suggestions? There are ~ 100 countries on the map.