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.
Silly semantic argument, but I have no objections to the definitions given above by Thorham. Makes as much sense as any other definition.