I know this is a tall order, but I want this incremental.

That is, we should have two public APIs here:

  /**
   * Fully blame a file and return the list sorted by lines.
   * This method blocks until all lines have been covered.
   */
  List<BlameEntry> getBlame() {
    List<BlameEntry> r = new ArrayList<BlameEntry>();
    for (;;) {
      List<BlameEntry> step = getNextBlame();
      if (step == null)
        break;
      r.addAll(step);
    }
    Collections.sort(r, new Comparator<BlameEntry>(){
      public int compare(BlameEntry a, BlameEntry b) {
        return a.range.start - b.range.start;
      }
    });
    return r;
  }

  /**
   * Compute the blame for one portion of the file.
   *
   * This method returns as soon as one or more regions can be
   * proven to be the responsibility of a particular origin (commit).
   * The regions can be any part of the starting file, but will never
   * overlap with a region previously returned, or that will be in on
   * a future call.
   */
  List<BlameEntry> getNextBlame();

That way EGit can implement an incremental blame view like git gui does, and users can watch it fill in.  Obviously we'll run getNextBlame() on a background worker thread, but as soon as a block is ready we can forward it to the UI thread for painting.

Since we have to have a queue anyway to keep track of the regions we have pushed off onto our parent, we can easily return back from getNextBlame() with the regions we couldn't blame onto the parent and that the current commit needs to take responsibility for.