Hi mates, I'll try to give some tips, as I live in Prague and have riden this way 2006. It may seem long ago, but the situation stayed quite the same. And can speak only about the Prague - Buda direction and the czech point of view.
You can rent a bike in Prague, but I am affraid you'll be obliged to get thhe bike back in Prague as well.
link to bikerents in Prague:
http://www.firmy.cz/Remesla-a-sluzby/Pujcovny/Pujcovny-sportovnich-potreb/Pujcovny-jizdnich-kol/kraj-praha We choosed an interessting Route via GreenWay Prague-Viena, than along Danub to Bratislava, along Danub to Gabcikovo Nagymarosz (a big water damm), Gyor, Balaton, Budapest. it was a 6 day long trip with 5 day biking and 690 km, you can modify it in time or distance of course.
What I do very much recommend:
Prague :-)
the northest ppoint of Austria - an old border and military point
the rests of the iron curtain
southern Moravia - - the czech wine region - great impressions guaranteed
Vienna
Bratislava
Gyor
Balaton
Budapest
more about the Prague viena greenway you can finf on greenways.com I guess
Czech, Slowak and Hungarian Republics are save countries. Just watch your stuff, do not let your bikes unlocked alone. Always lock them, or better take them with inside, do not let them alone. people should be more or less friendly, the young people should speak some foreign language, mostly english, or german, the older generation speak german and russian rather than english.
About tour providers I can't say anything as I prefere just free traveling without much itinery and planning. From my point of view the're not wotth the money, as they offer something I do not need.
If you have concrete questions, ask, I'll try to answer if I can..
