Same universe but a different story set much earlier. You'll feel some slightly comfortable familiarity.
Glad you like Fire Upon The Deep! Agree with the previous poster, Vinge's Marooned in Realtime and The Peace War are not too shabby either. It's on my list of personal favorite sci-fi. Which in case you're interested since you sound as excited about Fire as I was, lessee if I can find it...
*copy and paste*
My personal favorite sci/fi, not supposed to be the most influential or most important or "the best" which really should always vary by a reader's taste, just to my taste.
Gateway - Pohl
Fire Upon The Deep - Vinge
Rendezvous With Rama - Clarke
Downbelow Station - Cherryh
Startide Rising - Brin
The Uplift War - Brin
Deepness In The Sky - Vinge
The Pride of Chanur and followup trilogy - Cherryh
The Mote In God's Eye - Niven
Titan - Varley
Ringworld - Niven
Foundation Trilogy - Asimov
Beyond The Blue Event Horizon - Pohl
Dune - Herbert
Ender's Game - Card
Speaker For The Dead - Card
1st 5 or 6 books of Zelazny's Amber series
The Forever War - Haldeman
Forever Peace - Haldeman
The Forbidden Tower - Bradley
Hyperion - Simmons
Barrayar - Bujold
The Many-Colored Land - May
Jem - Pohl