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. :(