I thought it was referring to the planet being "deep" in the sense of being in one of the lower zones of thought. And the Fire was the conflict of galaxy-spanning import that was playing out there.

But maybe there was more to it?

By contrast, the meaning of the title of the sequel "a deepness in the sky" is fairly literal once you get to know more about the alien species and their habits.

Besides other commenter’s suggestions I assume it’s also a reference to the opening of Genesis and darkness was upon the face of the deep.

I remember from somewhere (A forward?) that he originally titled it "On the world of the tines", but an editor suggested A Fire Upon the Deep instead. Sounds cooler? There's a connection to the story as it develops.

I always thought it was because AI dominated the shallow parts of the galaxy, but there was something that wouldn't let it expand down to the deep.