Seems like Germany is generally bike-friendly in terms of having lots of marked bike paths + bike routes + bike maps. I agree that that lots of northern Germany is a bit too gentle for me to want to spends lots of days riding there. Even more so the Netherlands.
Munich: I've found a lot of pretty farmland terrain with an agreeable degree of hilliness in Bavaria / Bayern, especially the southern part toward the Alps, so I would consider as a city Munich (which I've ridden in and out of, seemed not too difficult, following a bike map we'd bought).Certainly some of the "river tours" around Germany (e.g. Donau/Danube, Rhein) are set up to be friendly to a first-timer bike tour with easy accommodation + easy navigation -- and there are English-language bike guidebooks. (I think the Donau passes not too far north of Munich.) I've seen reports from English-speaking visitors who had a wonderful time that way -- but for me seems like too much too gentle.
There are other routes with more variety of hills in range of Munich, marked with signs on the road with maps + guidebooks (in German) -- like one east-west across southern-most Germany, between the Bodensee (lake Constance) and the Koenigsee (in Berchtesgaden park).
Paris: I've found some nice single-day rides in and around Paris. But not so clear that best multi-day touring routes in France connect well to riding into Paris -- (but you could take the train there after some other touring).
Rome: The region + roads around Rome don't seem so well set up for bicycle touring -- Doesn't come to mind as a first-timers area. Though I did think it was interesting to ride in and out of the city one day, I wouldn't rate the city itself as highly bike-friendly.
Switzerland is generally well set up for first-time bicycling + touring of all sorts on a variety of terrain connecting to like Lausanne or Zurich, but not likely to be the least expensive.
Ken