http://www.beyond.fr/sports/velo.html#rental

A nice website for cycling in provence .Lots of useful links to bike hire shops etc.Did the Cadenet Cycling route and Lavender trail as recommeded by this site and also part of the Luberon cycleway in june 2 years ago.In Haute Provence(Note Provence is vast of covers a large area),you can structure your ride so it is relatively downhill(or up hill) nearly all the way.Villages are usually perched though when you pass by which means a short steep climb en route.The bike rent shop in Forcalquier where I started had both Tourers and Mountain bikes for hire.