I read Fire Upon the Deep first and liked both books.

General recommendation is to read them in order (Fire first, Deepness second) but I don't really think it matters.