Adobe Illustrator e Corel Draw.
São ambos programas de edição vectorial, o ideal para anúncios. Tens ainda o Freehand, mas não te aconselho porque está prestes a ser descontinuado pelo Adobe em favor do Illustrator.
Se quiseres fazer publicidade para uma revista, por exemplo, podes ainda usar um programa de paginação como o InDesign ou o Quark.
O meu conselho final é Illustrator + Photoshop para retoques de eventuais imagens que uses no anúncio.