I used to design all the billboards in phoenix AZ.
We used Corel Draw, Illustrator and Quark on the mac.
Corel is clunky and slow and is your lower priced desktop publishing software.
Quark is a step above Corel, but is very hard to get used to using and has a learning curve.
Illustrator is definitely #1 on my list, I don't know if I have a bias since I've always used adobe products but it has the least confusing interface, smooth, solid, quick, integrates with anything else. Also costs the most.
If you're starting off with desktop publishing, definitely start with Corel since it's cheap.
If money and time don't matter to you, go buy Illustrator and do what you need to do to learn it.