It is actually fairly easy to travel Corsica by bike. Unless you want a "full package", including guide and pre-arranged lodging, you really don't nead a tour company. Just pack your bike and bags, book a flight to Nice, France, then a ferry to Bastia - and your good to go! (you can also fly to Bastia directly - of a few other costal cities - but it is generally more expensive. Plus the ferry ride is cool!).
There are small hotels and hostels, B&B, etc. just about everywhere. No issues either finding food and water. Even the small mountain cities are well served.
I would just avoid the June-July-August period, as it can get really hot and there are zillions of tourists. Best period is April-May or September-October. Plus at that time, there is really no need to book lodging in advance (and they will be a lot cheaper).
I did that in 2000 with a small group of friends. Our tour started in Bastia and we cycled the cost counter-clockwise - with an few days in Sardegna - ended in Bastia 2 1/2 weeks later. And it's in the plans to eventually do it again.