TL;DR : Greet them gently with a nice word and a smile (and a hand-shake if you feel like it will be welcome/appreciated...)
Not to argue whether the country or company culture is annoying or not, or should be followed or not, I believe that we shall focus on OP question : "It's more of a country tradition I'm against" and "How can I try to go against such a tradition without being rude?".
If you are known by your colleagues as being a foreigner, there's nothing rude at explaining your point of vue (ie: in my country, we have laws saying... / it's considered rude to... / I'm used to shake hands all the time...).
EDIT : in comments, OP says he's French. I don't think it makes any difference for my answer though.
If you don't want to say anything about that, just act as you want to, they'll get used to it after a couple of days. Just shake hands to everyone. My advice: in order not to be bothered, make the first move, friendly. Add a gentle smile to your hand moving towards them :)
Nowadays, lots of women like to avoid the cheeks kiss, as, as you said, men and women should be treated the same way, in a professional manner (*).
I worked with women. Some of them were happy to come to you and kiss, some would come and shake hands. Fine. Some would just say 'Hi', as their culture forbids touching a man. Fine.
When it comes to shake hands, I usually do that with a tiny move of my head, slightly like bending. Many cultures do that too. It shows respect without being "too much".
Respect is the key, either way. Be nice, friendly if needed, respect them, they'll do the same.
(*) as many related material found was written in french, I link to a BBC news thats targets workplace kissing. It's about Germany, but was widely spread in french newspapers as well, as the same problem arose all around forums of all kinds. YES, in France, women are more and more annoyed with men pecking on their cheeks.
I don't know if it's worth mentioning it, but my other half is French and definately hates this "tradition". As well as being called "Mademoiselle" instead of "Madame" just because she is not married and just around her 30's. All men behaviors like these are even openly debated, some are even regulated by laws about equity : titles, salary and so on...