"As soon as cycling races started" is probably one way of answering your question "when and where the first podium girls appeared at a cycling race?"
I had a look at Greek art related to sports. A lot of it shows women which seem to meet the Greek ethos of female beauty. On that basis I would argue the idea of attractive women accompanying male sports winners is as old as sport. It is unlikely the first presence of a podium girl at a cycling race is documented, but I think it is safe to assume they were pretty much always there.
I know it was goddess Nike and not just a civilian, and I'm sorry if you were after a specific event name, date and location but hopefully you can see this as one way of answering your question.
If you were after the oldest specific, traceable record/mention of a podium girl at a cycling race, then you may want to reword your question.
Examples below - possibly NSFW.
From this

From this

From this

From this
