At Torchbox (original creators of Wagtail) we rent servers with
Bytemark, who we recommend enthusiastically if your primary audience is in the UK.
For cheap, virtual servers, we like Digital Ocean, but Linode should be fine too. Many of our friends are proponents of Heroku, but we don't know it very well. Wagtail runs on Heroku, but the installation process is less standard.
Depending on traffic, you could run several Wagtail sites on a single small virtual server, but if your clients need SSH access, e.g. to modify their own templates, it will probably be simpler and safer to restrict each client to a single server.
Good luck!
Tom