There are many vector coastline datasets out there suitable for importing into your favorite drawing package. If you're into vector data sets. Another option is to find an online atlas picture that represents what you're after, do a screen grab of it, put it into a background layer, and draw your work on top of it. http://en.wikipedia.org/wiki/Roman_Empire has a basic map of the area that would make a good starting point (and it's even in SVG to simplify the appropriation). Maybe http://en.wikipedia.org/wiki/Roman_Republic would work because you're after Republic rather than Empire, but the principle is the same.

Style is always a tough one. A good starting point for might be http://en.wikipedia.org/wiki/Early_world_maps as it has a number of good examples (everyone loves the Tabula Peutingeriana).

Now add hard work and stir...