Say Medic got to Paris with 3 blue cubes but didn't have enough action to remove cubes, and a next player cures blue. Do we get to remove those blue cubes from Paris right away or do we wait till Medic's next turn?
The blue cubes in Paris are removed immediately:
From the Rules (Classic Pandemic p.5), emphasis mine:
The Medic removes all cubes, not 1, of the same color when doing the Treat Disease action. If a disease has been cured, he automatically removes all cubes of that color from a city, simply by entering it or being there. This does not take an action. The Medic also prevents placing disease cubes (and outbreaks) of cured diseases in his location. The Medic's automatic removal of cubes also happens during other players' turns.