A few of the default Debian packages give feedback messages like "This could take a long time..."

Most of them used to take a long time, but hardware has caught up. SSH key generation, locale installation. Instead, it's a warning that briefly appears on modern systems, but is visible for quite a while on, say, a Raspberry Pi.

I designed and maintain a report-generating component and my system does the same thing. (Plus it is helpful as users can tell me where in the process it failed/hung) It doesn't matter how long each message sits on the screen, as long as it changes every so often. Animated, infinite progress bars also help if you don't/can't estimate ETA

A cycling animation only tells you that your computer/UI isn't dead, it doesn't tell you that the underlying task isn't frozen.

In the loading animation of windows 98 there was a horizontal bar of moving colors. And if it stopped animating, you can be 100% sure that the computer is frozen. I wonder if we can do similar with cycling animations.

Can it not say "$X items processed..." or have a spinner that updates it's frame at certain intervals? It doesn't have to be a percent, just proof of progress. I had no trouble adding an accurate "$X rows of csv processed" in a laravel (PHP) + VueJS app.

I know this won't work everywhere, but if you know how much time the task generally takes, your progress bar can just be a timer for that duration. Still more informative than fake messages.