Cheek kissing is a very discussed topic in each site like this, because it is quite different depending on the country (number of kisses (especially), when to cheek kissing, men/women...) and it is a thing a foreigner will do even in a short stay. There is a lot of information on the internet about each country culture respect of it, like this map of France.
I didn't ever think about which side should be kissed first, until I moved to (southern) Italy and I had a few of embarrassing situations because here they start kissing left cheek, i.e. moving the head to the right. It is even more embarrassing when men also cheek-kiss here. Then I realized in Spain we always start kissing right check.
But I didn't find information (regarding a few sentences on Wikipedia) about this matter. Is it any cheek-kissing-depending-on-countries collection including it? Maybe it is more stablished in countries with an odd number of kisses?