When does the App Engine scheduler use a new thread vs. a new instance?
If I set threadsafe: true in my app.yaml file, what are the rules that govern when a new instance will be created to serve a request, versus when a new thread will be created on an existing instance?

Like people are saying here, if a previous instance is already using 10 threads, a new instance with a new thread would be initiated.  A new thread will be created if all other threads are busy, they must be either waiting for some response or with computing results.

If I have an app which performs something computationally intensive on each request, does multi-threading buy me anything? In other words, is an instance a multi-core instance or a single core?

Now this question is very controversial. Everyone knows the answer but still they are skeptical. Multi-threading can never buy you any good if your task is based on just computations unless you're using a multi-core processor, don't ask me why a multi-core processor will help better, you know the answer. Now google app engine is not sophisticated enough to decide that when new threads should be dispatched to the other processor/core(if it exists), only new instances are dispatched to the other core/processor. Want your thread to run in the other core/processor? Well, throw some skills there and booya! Remember, it's upto you to decide if threads should run in other cores/processors, the engine can not take the responsibility for such because this could lead to so many confusions, the engine is not God. In short, by default the instance is single core, the engine can't decide for you when it should go multi-core.

Or, are new threads only spun up when existing threads are waiting on IO?

The first part of my answer clears this out. Yes, they only spun up when existing threads are busy, this is how threadsafe works, to prevent deadlocks.
Now I can tell you this all, from my personal experience, I worked on the app engine for many months and programmed/debugged/tested apps that were highly dependent on the threadsafe architecture.  If you want I can add references(I don't have references, just personal experience, but I'm ready to search and put things on the table for you), but I don't think they are needed in this case, threadsafe works in obvious ways which I have validated myself.
If I set threadsafe: true in my app.yaml file, what are the rules that govern when a new instance will be created to serve a request, versus when a new thread will be created on an existing instance?
If I have an app which performs something computationally intensive on each request, does multi-threading buy me anything? In other words, is an instance a multi-core instance or a single core?
Or, are new threads only spun up when existing threads are waiting on IO?