Exactly. Honest (but poorly implemented) bars teach users not to trust them. This is because the time estimation they are attempting is inherently hard. Many kinds of computation cannot be estimated without actually performing the computation.
Yet, users want progress bars anyway. Without an apparent, finite timeline, they get frustrated and angry quickly. Thus the conflict.
So, the recommendation I’ve seen is 1) work very hard to get as smooth and linear if a bar as you can. And 2) fudge the numbers to give it a bit of acceleration to counter the user’s decreasing patience.