Presumably you cannot use the ArcGIS.com base maps? It might help to know what mapping software you're using. Most base maps are projected into web Mercator projection, so if that's not a problem, there are many choices.
A good option would be TileMill's base layers. You can style them however you want and then export as vector for refinement in Illustrator or Inkscape.
The problem with the ArcGIS base maps, is that they are tiled rasters, so you'd need to trace them in a vector editor, which isn't ideal.
If you don't mind getting your hands dirty, there are plenty of shapefiles available with first, second, and third order administrative boundaries.