I personally don’t know much about Pyrenees but I know theres easyjet airports and mountains…
Majorca would be good, I’ve been twice and would still go again.
Sardinia is on my list for a cycle holiday and there are big hills but v difficult without a car I reckon.
Innsbruck?
Freiburg would also be good, fly into Basel and explore the black forest.
Probably depends what % you want it to be a pure cycling trip vs a weekend break w/ bikes