Bluehost, USA - shared hosting, package is most basic. Superb through over 10 years, with various websites. I learned about Wordpress going through its options.

However, for one of our websites with tons of pages, creating a sitemap using a cron made it throttle the CPU, and since it is a shared hosting, cron job is stopped.

For this intensive memory use, I put the sitemap creator cron job in Gator shared host, but pointing to Bluehost. No problem.

So Gator is another alternative.

I know you said Europe, but I am from Singapore, and using a US hosting service (Bluehost, Gator) has been very reliable. In Singapore, the prices are incredibly high, like 10x ...