Another recommendation, not a first contact story, but a very weird world and you wonder why things are how they are:

Inverted World by Christopher Priest