The majority of rental cars in Europe are fitted with a manual gearbox. If you need an automatic, then you must explicitly book a category of car which says that it is an automatic, because the chance of getting one any other way is slim. This applies regardless of which agency you want to use. You will find that for small cars the premium you pay is significant and if you go for high end cars, where automatic boxes are standard, they will be extremely costly compared to smaller models.

Sorry, but that is how it is.