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.

You can start with the second, but the first book is better at grabbing the attention of a new reader with wild ideas (broadband audio hive-minds, variable speed-of-light). If you make it through the first chapter you won't be able to put it down.

The second book is just as good, but doesn't try as hard to get you addicted early on. The assumption is that you already know how good Vinge's work is.

I recommend starting with Fire Upon the Deep.

A Fire upon the Deep and A Deepness in the Sky are loosely connected; you can read them in either order. Both novels reveal some details which explain bits of the other.

However, I would recommend skipping Children of the Sky. It's not as good, and was clearly intended as the first installment of a series which Vinge was unable to complete. :(

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.