You are essential describing the difference between progress that has a determinate status and one that has an indeterminate status. The 'bad' user experience comes from not applying the correct design pattern to the right type of status and also letting the user know what the relative length of wait time might be. When it comes to waiting time, the key factors are the user expectation and the correct or accurate representation of wait time.
When you know the tasks to be completed and the amount of time it will take (hopefully it doesn't change during the process because it is based on some variable like connection speed), then it is appropriate to show a progress bar that reflects the relative completion status of the task. However, if it is not possible to be even relatively accurate then you can manage the user's expectation by showing them that it is going to take as long as it takes.
And if you can manage the user's expectation correctly, they are prepared to wait or go and do something else while waiting. If you provide an accurate representation of wait time, then they know roughly how long it is going to take and can therefore manage their own expectations and make a decision about whether to keep waiting or cancel the process.
If you really can't work out what the length of wait time is, and have no real way of managing the user's expectation, it is still possible to provide a good user experience by allowing the user to do something useful or entertaining during the wait time (e.g. provide a mini-game or show some interesting information/facts/trivia).