The first two books can be treated largely as standalone works. They do technically take place in the same broad universe, but said universe is basically divided into FTL and non-FTL zones with vastly different societies in each (for obvious reasons), and the non-FTL societies aren't even aware of this boundary. "Fire upon the Deep" is set mostly in the FTL zone, with the boundary itself being a major plot point. "Deepness in the Sky" is set entirely in the non-FTL zone, and the lack of FTL is a major plot point there.

Chronologically, DitS takes place before FotD. But there is exactly one character in common between the two books, and while he is a major character in both, none of the events of DitS are relevant to the story in FotD (which makes sense since FotD was written first).

So it's really largely a matter of preference as to which one to read first. I would say that FotD has more action and, for the lack of better term, "weirdness" in the setting; while DitS is more slow-paced, with more character development and generally more fleshed-out characters, and explores its themes deeper. But both books have plenty for your mind to chew on.

All in all I think FotD is an easier read, and DitS is a more rewarding one, but this is all very subjective.

One upside to the books being decoupled as much as they are is that whichever one you start with, you get a complete story, so even if you're a completionist you can disregard the other book if you don't like the first one.