Hi bobbydb and welcome to the forums.
Having multiple sites hosted with the same company shouldn't be a problem. Having multiple sites hosted on the same server and all linking to each other might be. If there is a genuine reason why they are linked, then Google should be able to spot the difference between that and link farming, so unless you're doing something dodgy, I don't think you need worry. (And 123 is such a large company that the chances of your sites all being on the same server is pretty remote.)
Are you looking for UK hosting? I have several small sites hosted on shared hosting with UKHost4u and have had no problems at all.