My take:
A program is anything from applications to utilities to games to scripts.
A Utility is a program like Directory Opus, PowerPacker, LZX, etc.
An application is a program like Brilliance, FrexxEd, Protracker, etc.
In other words, utilities are programs that help the user do things, while applications enable the user to be productive, while programs are all of these things and more.
