Yes I've used Vidahost for a long time now. I don't know how I originally stumbled across them as they were relatively new at that time, but I was looking for a new host after the likes of 123.reg and easily hadn't been working out because of the amount of site traffic.
Everywhere else was saying I needed dedicated, but Seb and Dom back in about 2006 put together a bespoke business package for me at a reasonable cost. Since then, and as the site grew further I've upgraded several times through with them and my experience with them has been on the whole very good.
However my requirements are obviously more than the average user, so Ive no experience with their general shared type hosting.
-----
Talking of small hosts, there is also our own
d2d4j who runs a hosting company and is extremely knowledgeable.
He offers special rates for members of this forum from time to time which may be worth looking at.
linky