> I know I should give users feedback as to what stage a large software
> application is in while first being executed...But what should I say:
> "Go get some coffee, this is goina take awhile".
> 
> Seriously,
>         What are some typical messages?

First of all, don't start a resource-consuming job without
explicit user ok.

If there is a possibility of failure, log progress to a file.

If possible, state an expected completion time, updated regularly
if you only use an heuristic.  This is typical for file downloads,
printing, disk scans and so on.  When you have an estimate of
completion time, also provide a graphic representation (progress
bar), since it's easier to see at a glance how far progress is, or
if program has hung itself (sad, but a necessity nowadays!).

Provide some means of notification when the job is completed.

Provide some short indication of what's been achieved and what's
going on right now.

If it makes sense, provide a means to obtain more detailed info.

If possible, give an option to cancel the ongoing operation.  But
if you do, it would be nice if cancel was disabled when no longer
available (I never trust the cancel button of an install program!).