> Leiningen (the Clojure build tool) is written in the JVM, and on my machine it always takes 5 seconds just to start.

The lein help command does more than simply print a string, it searches for plugins available on your system. To measure the startup time of lein perhaps you should do:

  % time lein version                                                           ~
  Leiningen 1.6.1 on Java 1.6.0_26 Java HotSpot(TM) 64-Bit Server VM
  lein version  0.75s user 0.05s system 130% cpu 0.612 total

Less than a second, not bad.

> time lein shows about 10 seconds to display all the output, and then it hangs for about a minute more before the process completes.

So there's a problem on your system. Most people don't have that problem. Check your plugins.