it _IS_ hard, but no reason it can't be done better.
take "stuff to do" (steps, gigabytes, number of files to copy) and divide "stuff done" into it for "fraction complete".
Put that "fraction complete" into a proportion with "time taken so far" as the known item and "total time" as the unknown.
Apply some inertia or hysteresis to the "total time" so you don't have it rapidly jumping all over the place (like file copy dialog estimates seem to).
This total time estimate relies only on knowing what _HAS_ happened at a given time, not on predicting what _MIGHT_ happen on a user's machine.
Apply "fraction complete" to the length of the progress bar, and report the expected remaining time as text.
The bar is for "progress", and mustn't go backward unless "progress" does so as well (maybe when you cancel an install? This is an edge case). The estimated time can vary as needed - but gee, maybe build some logic into the dialog to let the user know to bang on the side if it looks like something's hung.
You could trend completion speed ("that part went fast, you're slowing down now") as a sparkline or other visual decoration (color map - green for fast, red for slow) to give the user more confidence that the dialog knows what's going on.
Under NO circumstances should a site or app put up an animated gif in place of progress (because it shows only that the browser's still running, not that any completion is taking place). Think of how often this happens today. Tragic.