Andorian skin color was Blue, but humans weren't the first encounter with the totally different skin color. They already knew Vulcans who possessed same pink-ish skin color.
Why did Shran really call Archer "Pink Skin"?
Originally, "Pink Skin" was an Andorian insult for humans, since what humans looked like was just about all they knew about us. I believe Shran coined it in The Andorian Incident, at the P'Jem Sanctuary - they were highly suspicious of us, since they were trying to uncover a listening post at the same time we happened to bring a Vulcan to the sanctuary.
However, at P'Jem, Archer uncovered the listening post and did not side with the Vulcans, as Shran expected. Because Archer was always fair in his encounters with Shran, and not simply siding with their then-enemies, the Vulcans, Shran became an ally.
Calling Archer "pinkskin" very quickly stopped being an insult or even necessarily a dig at his skin color: It's a sign of friendship, similar to us calling our close friends "shorty" or "fatty" in a joking manner, and can persist long after they've outgrown the reason for nickname.
EDIT: Here's the first occurrence in The Andorian Incident:
Shran: "Why didn't you tell us one of your people was aboard?"
Vulcan monk: "It's an Earth vessel, I didn't know."
Other Andorian: "What does that mean? 'Earth', what is that?"
Archer: "It's where we're from. It's our homeworld."
Shran: "Why did you come here? Answer me, pink skin!"
No reason was explicitly given, but this exchange happened moments after Archer and Trip had wrestled down one of the Andorians. They were a bit red in the face from the exertion...
Shran called Archer "pink-skin" because humans who have fair complexions like Archer appear to have pinkish-colored skin, especially when compared to the blue-tinged skin of the Andorians. The pinkish color of the skin is due to the redness of our blood.
Skin color ranges from almost black to white with a pinkish tinge due to blood vessels underneath.
This is in contrast to Vulcans, who don't have red blood: they have green blood when oxygenated, causing Vulcans with fair complexions to have green-tinged skin. The only apparent pinkishness of their skin that the audience sees is simply due to human actors playing them. Vulcans—like most alien species in Star Trek—aren't given heavy makeup treatments, and their skin isn't recolored like Andorians are.
Shran purposefully exaggerates one of Archer's features to denigrate him: Archer's skin isn't blatantly pink, just like Vulcan skin isn't blatantly green. By highlighting a superficial difference like Archer's skin color, Shran reinforces that humans are not like the "superior" Andorians, much like calling a Vulcan "pointy ears".
On the other hand, calling a Vulcan "pink skin" would've made as much sense as calling a human "pointy ears" because in universe, they don't have pink skin just like humans don't have pointy ears.
Andorians have bold skin tones, and so references to skin colour may be an Andorian tradition. In "The Aenar", J'hamel (an Aenar, who all seem to have white skin) refers to the first time she saw a "Blue Skin". The daughter of Shran and J'hamel ("These Are The Voyages...") has green skin, although this may be due to her unusual parentage.