I can think of at least two approaches from classic project management that could help here. I used to do UX design for Microsoft Project (a long time ago), so that's why I'm biased into looking at some of those long-established styles.
Before I get into specifics of layout and drawing, though, I will implore you to limit chart junk--extraneous lines and edges that don't communicate any information. I know that your ASCII art is just illustrative, so I'm not trying to critique it. However, it's easy to fall into drawing lots and lots of boxes so that the edges of the boxes (which are usually information light) end up taking up lots more mental space than the contents (which are usually information dense). Whatever approach you take, make sure that anything that's a line or edge is really a useful bit of information, and consider how shading, whitespace, and other techniques can communicate information, too.
One is to use a PERT-style chart (really a graph). This shows each project or task as a box and lays them out so that predecessor tasks are to the left, successor tasks are to the right, and links them with arrows. You can change the style of the box to show different properties of tasks--like using color, shape, icons, or other decorations to show project, complexity, duration, number of resources, and so on.
I would draw you an example, but a Google/Bing for "pert chart" will show you lots of different variations, and it sounds like you're trying to cast your net wide, rather than see specific applications at this point.
Another idea, which is a bit more focused on task duration, is to draw a Gantt chart and show arrows between the bars, reflecting the dependencies. Again, there are lots of great examples with a web search for "gantt chart," so I won't try to draw anything here.
You can also try a hybrid approach, where the width of your boxes is determined by something like duration or hours of work, or the left edge of the boxes is determined by a rough start date or milestone.
You mentioned tooltips, and these are a great way to show more information, too. There is likely some deeper data which can help inform understanding of the project, but would pollute the overall display. Being able to hover and see more, or to click and get a popup of properties, might help you balancing depth of information against simplicity of display.