I haven't read any Vinge, but I do have some works related to first contact that I want to recommend.
Firstly, I am yet another supporter of Carl Sagan's
Contact. The beginning is rock hard sci-fi; an incredibly plausible account of how our first communication with an alien species might go, and how to interpret their messages. The science gets softer as the book progresses, but its strong characterization and themes about faith and evidence continue to carry it through to its amazing end.
I also recommend
A for Andromeda. The plot starts out like a version of
Contact that takes place in the 60s rather than the 80s, but the focus is rather different. There are a lot of interesting interactions going on between characters, as well as intrigue between political groups and companies. It's definitely worth a read if you can find a copy.
Finally, I recommend Eliezer Yudkowsky's
"Three Worlds Collide". The first thing that everybody mentions about it is that it starts with baby-eating aliens and goes from there, which pretty much sums up the free online novella in a single sentence. By far its biggest selling point is that it shows something that is rare in sci-fi:
alien aliens, with inhuman culture and biology. Combined with an interesting presentation of game theory concepts and amusing writing, this is one of the best sci-fi stories I've read in a long time.