Would an easy way to improve this be to provide some status info in the log window below the progress bar, even when not in verbose mode? I usually run with verbose mode, where the log output clearly shows there is something going on, but I've also seen new users struggle with the same uncertainty about what the IDE is doing.

I agree, a clearer (animated?) progress bar could help a lot to understand that the IDE is doing something while it looks stuck (silent mode and Windows combination). I'll try to hack up something to test it on the various OS/DE combinations.

Shitty example of a possible implementation (preserving the OS native Look and feel)

diff --git a/app/src/processing/app/EditorStatus.java b/app/src/processing/app/EditorStatus.java
index 2dfc8cf25..8487e5c65 100644
--- a/app/src/processing/app/EditorStatus.java
+++ b/app/src/processing/app/EditorStatus.java
@@ -193,10 +193,31 @@ public class EditorStatus extends JPanel {
     setCursor(null);
   }
 
+  static Thread progressThread = null;
+
   public void progressUpdate(int value) {
     if (progressBar == null) return;
+    if (progressThread != null) {
+      progressThread.interrupt();
+    }
+    progressBar.setIndeterminate(false);
     progressBar.setValue(value);
     repaint();
+    // Repaint in a new thread
+    progressThread = new Thread(new Runnable() {
+      @Override
+      public void run() {
+        try {
+          Thread.sleep(1000);
+          progressBar.setIndeterminate(true);
+          progressThread = null;
+        } catch (InterruptedException e) {
+          // do nothing
+          progressThread = null;
+        }
+      }
+    });
+    progressThread.start();
   }
 
   public void paintComponent(Graphics screen) {

That's better than nothing.

Any idea why the builder spends so long on some systems not sending any progress updates?

Well, it only emits a progress message when a complete "step" is executed (not for every compilation unit) and we can solve this quite easily. But the biggest problem is the startup overhead (libraries, tools and cores scanning etc) which is painfully slow on slow hard disks; this can only be mitigated by scanning once and then living as a daemon, as we started to do in the beta branch.

For the first problem I pushed arduino/arduino-builder@a32d158 . Replacing arduino-builder with the one provided by @ArduinoBot makes the progress way smoother (it's still a hack, anyway).
I'm merging the changes in beta quite soon so it can be tested more easily.

Looks like arduino-builder is printing plenty of info when run in verbose mode.

Maybe the IDE could always run builder in verbose mode and parse the verbose output (ignoring the worthless info progress messages), and simply not print the compiler commands when the user has verbose mode turned off?

The early compiler commands during "Detecting libraries used..." seem to have plenty of info about the library locations. The IDE could pretty easily allocate the first 10% or 15% of the progress bar to this phase. Then as the directories become known, it could read those directories to know how many times the compiler will need to be run (or files reused).

Is there any chance to add more progress output to arduino-builder for the 1.8.7 release?

Even some messages telling the IDE when each stage the build process is started and a progress message as each file is handled would allow me to try to craft some code on the Java side. Hopefully just emitting those messages in the format the IDE parses (and doesn't show to users) would be pretty simple to add?