Most reputable hosters have no real interest in their customer's business ideas because they're in the business of hosting. Any hoster stealing business ideas would quickly lose out on reputation if they crossed that line.
Speak to a company that does dedicated servers and chew the fat with them about your requirements.
Without knowing what your solution does and what special needs it has you're not going to have much luck getting qualified answers on SO. So maybe an overview of what you're doing without giving away the crown jewls would be in order.
Update: Right....there's a lot of FUD here about hosters stealing customer business ideas. I work in the hosting business and have done so for over 10 years....
Professional hosters really have no interest in your business ideas....they're in the business of providing hosting services, not building the next StackOverflow or Amazon or EBay or whatever. Do you really think CrystalTech (who host SO) thought "oh hey we could do that and make a pile" when Jeff mentioned the project idea? No...they do hosting.
Many professional hosters have reseller programmes, and those hosters that do take great care not to step on their reseller's businesses with shoddy practices like contacting reseller customers directly to steal their business.
Professional hosters have enough on their plate making sure that their operations run smoothly such as managing 100's to 1000's to 10,000's of servers, ensuring that backups work, ensuring that servers don't cook in the DC, ensuring that network connectivity works properly, ensuring they get paid etc etc.
Professional hosters often have staff available for value add services such as consultancy and technical support to help you the customer get your business idea off the ground, and as fascinating as your business ideas may be, that's all their guys are employed to do. If you're really that worried get them to sign an NDA before you speak to them. I've signed plenty in my time and have seen some fantastic businesses get off the ground and make heaps of cash....but....those businesses are not my area of expertise....because guess what....hosters do hosting services.
The company I work for started off in the hosting business in 1998 by being a reseller for a large US hoster, at the time we had 10 dedicated servers with them 3 of which were shared and raked in a pile of cash @ $15 a month per site with around 600 sites a server. The profit margin was very lucrative....did they steal our business?...nope.
So my advice to Jonathon is go speak to a good hoster and talk things over, get expert advice.
Hosters do hosting, we're not interested in selling pies or widgets or becoming the next venture capital darling for the next flashy Web 2.0 idea.
Cheers
Kev