I currently work with ArcGIS 9.3 and have decent competence with Adobe CS4-5 of Photoshop and Illustrator. I'm more than happy to branch out to other software.
Essentially, I'd like to get really good at creating maps that look like old maps with unknown "there be dragons" areas. One project I have in mind is maps of old spice trade routes. I'm thinking of a Art Noveau style like Alphonse Mucha. I get a kick out of imaginative maps that are aesthetically pleasing, simple, and easy to read.
This isn't exactly what I'm looking for, but yes, in this general direction. Map-poster from Conservation GIS 2011 Contest
Best Answer
James Fee had a post about some resources to make historical map effects using ArcGIS. A zip file of all the materials including icon and font sets are available.