I imagine that the reason that Ice forms first on bridges is that the bridge is isolated from the ground. It can cool off faster, and hence the ice can form first.

The ground does not cool down as quickly as the air surrounding the bridge, however water cools down more slowly than land. Thats why Moscow is much colder than, Dublin say, during the winter even though they are as far north as each other.