> with some query it could take too much and the slowing down of the bar filling wasn't well met with both our users and our boss.

One idea I've toyed with, which adds some complexity, would be some random variation, so that you'd still get some faster jumps at the end, even though the average would be exponential.