Never going to find a universal definition, but my 2 bits:
I would, by modern definitions consider "apps" to be limited use software on limited use devices. Such as the "app" buzzword for smartphones and tablets. I consider iWork, Angry Birds, GarageBand on iOS all "apps", despite them being very different function and purpose wise. I don't use the "app" word for anything other than when in reference to SW on content consumption "appliances" like tablets, personally.
Utilities - I'd consider a program used mainly for the manipulation, conversion, or management of data. File managers, gfx batch converters, etc. DirOpus, Windows Explorer, backup tools, etc. Utilities are what I use when I "need to get shit done"

Utilitarian programs that facilitate getting a task accomplished.
As for Programs, I'd consider any piece of software that allows for the creation of content, media - what have you, a program.
Hell of a lot of overlap between the 3, obviously. Is ADPro a program? Sure. Is it also a utility? Absolutely.