There are of course two sides to everything. I have also been in the publishing business for a long time, with a degree in Advertising/Journalistic Management. I was advertising manager for a large oil company and owned my own newspaper for several years.
The people at the Kinkos and other copy places here are really not very professional. Most are young "kids" who will try to do what you tell them, and nothing more. Maybe they are better in your area.
I also use coated stock and do not work from the supplied templates in Publisher.
I will agree with Russ that a nice personalized letter with song list and photo work very well, if you enclose a CD.
The idea of a brochure is to get people to listen and judge you from your sound. Russ, I'll bet you have eliminated some good acts without listening to their music over the years by judging them from the appearance of their package, which is, I suppose, what you are saying.
Anyway, we're all only trying to help and offering the benefit of our personal experiences. There is a learning curve in any computer software program. Maybe it seems easy to me because of my background.
DonM