Here is a patch for this issue. The patch adds multiple job init threads in the EagerTaskInitializationListener, which is used to initialize tasks by the default scheduler (JobQueueTaskScheduler) and the fair scheduler. The capacity scheduler actually initializes jobs in its assignTasks method, which happens in an RPC handler thread, so it can already do this in parallel (although it may be worth modifying it to have a separate set of job init threads so that the RPC handlers don't block waiting for a job to initialize).
This patch also makes the CachedDNSToSwitchMap use a ConcurrentHashMap instead of a TreeMap for its rack resolving cache to avoid errors caused by multiple writes. (Cache-hit reads require no locks with ConcurrentHashMap.) Apart from the possibility of multiple writes to the resolution cache, I think I saw no other potentially conflict-inducing operations in initTasks, but I'd really welcome a second pair of eyes to look at it.
The number of job init threads is configurable as mapred.jobinit.threads. I set it to 4 by default, but let me know if there are any objections.