Strongly recommend reading A Deepness In The Sky before reading A Fire Upon the Deep. They're both good books but ADITS is phenomenal and much more similar to Accelerando, whereas AFUTD is less "hard sci-fi" and more "fantasy".
I'd absolutely disagree. If you read ADITS before AFUTD, you'll miss out on one of the major themes of ADITS - that you, the reader knows what's going on, and that the characters don't. That you know how it ends (well, ish), that you know the secrets they don't. That tension - maintained over such a large book - is what makes it so good!
I read ADITS, and then only got partway through AFUTD before getting distracted. You have me curious enough to consider a second attempt at reading through the latter. My parting impression of ADITS was just deep disgust and sadness about the human cultures.
Yes. Although AFUTD is set after the events of ADITS in the in-universe history (so ADITS is logically the prequel even though it was published later), the back story of Pham (who appears in both) is intentionally mysterious in AFUTD, and thus ADITS in effect contains spoilers if read first.