The University of Texas Libraries has a huge collection of maps:
Perry-Castañeda Library Map Collection
These maps are almost all public domain, available for use w/o copyright restriction. Those that are copyrighted are marked.
They also have what looks to be an extremely thorough collection of links to other online map sites:
Maps on Other Web Sites
Of course, maps from these other sites need to be checked for their own copyright restrictions.
Here's a site that will allow you to create a map of pretty much anywhere in the world. You can turn on/off geographical and physical features, and you can save them in various formats, including directly as Illustrator files:
Planiglobe
Maps created via this tool are creative commons licensed.
This site is full of inspiration:
The Random One wrote:Also, if you have a mind for the strange, I recomend the Strange Maps blog.
Incredible! Public domain, fully detailed, commercial quality, vector-art maps of the world!
CIA World Factbook Reference maps
These are in JPG and PDF formats. If you open the PDF in Adobe Illustrator you can edit the vector art - country outlines, political labels, etc. I haven't found a way to extract the EPS without Illustrator, but I suspect that it's possible.
Here's a very cool set of maps scanned from the original editions of Jules Verne’s novels.
The maps from the Voyages Extraordinaires
These maps are in the public domain, despite indications otherwise.