Ortelius is great, but I appreciate the flexibility of Illustator. I found Illustator pretty easy to learn, so if you're interested in mapping I recommend spending the time. Don't be intimidated by the complicated UI, you really only need a few tools.I used to use Ortelius (Mac only), but about a year ago I switched over to Illustrator. For anyone who doesn't want the price tag of Illustrator though, Ortelius is a great map-making tool. It's a pretty reasonable price too (I think it was below $50).
I just started using the line, curve and ruler tools and Googled my way to figuring out whatever else I needed to know.