The following is just a first approximation, and focusses on the Tour de France.
Most books I consulted either never mention any female in connection to the race and instead celebrate pure male heroism (and occasional misdeeds). Few do mention the podium girls vaguely, but then try to convince its readers that they were simply (as insinuated on another SE) 'always there':
Flowers and fluff - On arrival, always the same ritual. Hostesses, flowers, kisses offered to the victor and the 'maillot jeune'.
— Mustapha Kessous, Clément Lacombe: "Les 100 histoires du Tour de France", Que sais-je, 2013.
But that may not really have been the case from the very first race onwards, which appears to be initially a not very popular and male-only all around. Only with rising popularity the spectators 'diversified':
And Marcel Viollette was able to write in 1912
Few races are as popular as the Tour de France. There is no other race which produces such support. Think ofthe regions that it passes through, some of which never see any other sporting event from one year to the next! […] You have to have followed the race to properly understand the crowd that masses around the checkpoints or the joyful surprise of the good peasants as they see the bunch of good-humoured young men riding through the streets of their village at 35kph whilst still finding the time for a joke or a kiss blown to a pretty girl. And pretty girls aren’t in short supply along the route!
— Hugh Dauncey & Geoff Hare: "The Tour De France 1903–2003. A Century of Sporting Structures, Meanings and Values", Frank Cass: London, Portland, 2003.
An apparently dedicated fan has had as much trouble to ascertain this origin story as we displayed here so far in determining when a 'podium girl', 'hôtesses du Tour', 'Miss Etape' or a 'Reine de Sables' (that is here: 'local beauty queen') first appeared at the Tour de France.
Podium girls were originally selected from the population of the town where each day's finishing stage was held, and the only requirements were for them to be under 30 and about the same height as each other. (WP)
What can be said is that in the 1928 race and at its 6 station, a local beauty was instructed to show up and kiss the winner Oppermann, but obviously still with a 'podium'…
This is how most cycling races end: the winner gets on the podium, and is offered a bouquet of flowers and a few kisses by a pretty girl.
It is difficult to say when the tradition dates back to ancient times (as early as 752 BC, the Olympic champion received a crown of wild olive tree and a branch of palm tree).
If we look at the history of cycling, we can see from the illustrations that in 1896, on the occasion of the very first edition of Paris-Roubaix, the winner Josef Fischer received two splendid bouquets of flowers. It is thus in the continuity of a well-established tradition that in 1903, Maurice Garin, winner of the first edition of the Tour de France, also received his bouquet.
So much for the bouquet story. But the kiss from the lady... when was that?
That as well is hard to say. In the photos of the first arrivals of the Tour, we see mostly men with moustaches. The first lady appeared in 1928. On the photo, taken at the finish in Les Sables d'Olonne, we see the stage winner congratulated by a "Reine des Sables".
A few years later, in 1930, the Tour returned to Les Sables d'Olonne. André Leducq, winner of the stage and future winner of the Tour, then received a kiss of love, not from one but from two Queens!
From then on, it was often ladies in folk costumes who presented the winner with his bouquet of flowers, accompanied by a few kisses. The tradition is launched and it coincides with the birth of beauty contests, and the first Miss France elections (from 1927).
— 'Mart1': "Petite histoire du podium et de ses Miss", le 10 novembre 2009
This is as far as I got as well. Except that the oldest photo with a female at least in the frame I found was Henri Pélissier from 1923:
All this does not the appearance of podium girls before 1928.
On the contrary, some books claim the strict arrival of 'the podium' to be a requisite of 'podium girls'. (A History of Cycling in 100 Objects
By Suze Clemitson, Bloomsbury Publishing, 2017, p164) That is during the first race it would have been an all male affair, then women were gradually introduced 'for decoration' and the recognisable form came to be in 1947, although the only picture available to me from searches has again mainly men on the platform, despite winner Jean Robic clearly receiving female presence:
For comparison, La plus belle femme de France was first chosen in 1920, called 'Miss France' by 1926 and indeed this 'contest' underwent significant changes in 1947 as well.
Note: the newspaper most closely following events from this race L'Auto is archived at BnF Gallica. A search on this not always perfectly OCR'd daily with strings more cleverly chosen than what I tried might narrow this down better.
From the presumed scope it might also worth a try to look into "the best sports history book ever written", which I can't access, Benjo Maso: "The Sweat Of The Gods: Myths And Legends Of Bicycle Racing", 2005.