Based on the responses, many people are seeing slow times with "lein repl", which is generally *much* slower than just starting a normal Clojure repl with clojure.main.
If you want to compare, you can use lein to dump your classpath to a file (or the Windows equivalent of these):
lein classpath >&1 my.cp
Then start the stock Clojure repl using that classpath:
java -cp `cat my.cp` clojure.main
I think you'll find that the clojure.main repl startup is much faster, especially for bigger classpaths - for a new project with no deps it's about 5s vs 1s for me.
When you do "lein repl", Leiningen will launch an nrepl server, then launch a reply client that connects to that server via nrepl. reply integrates with jline to provide a lot of great command-line help, including completion (via clojure-complete). clojure-complete will scan your classpath to build up completions, incurring a fair amount of overhead. It seems like it does a lot of this work before you even get a live repl to work with - I have not been able to track down why that occurs, but it certainly seems unnecessary.
If someone wanted to work on improving that clojure-complete bit, it would help a lot of people (independent of anything we do in Clojure core). For example, it seems like the completion index could be created in the background and cached in an atom (with re-indexing if needed). Completions could just work from that atom - initially you'd have nothing while the index was being built, but at least you could start the REPL in the meantime.
Hard to say where to file an issue on this - it lies kind of across clojure-complete (which is not really set up this way) and reply which uses it. It would be cool if someone wanted to look into this further.
I didn't look into the nrepl server/client stuff, but I have to imagine there are probably things there that could be faster too.