I have setup insight block explorers and apis in the past, although those sites are no longer running as they were for now-defunct altcoins. I would recommend that you use Amazon AWS mostly because I am very familiar with the way that they work. Of course, you should run the instances with your AWS account.
As for cost, I created an estimate of the costs to run it on aws here: http://calculator.s3.amazonaws.com/index.html#r=IAD&s=EC2&key=calc-8E5EAF6C-B535-4315-B2D2-9521C361ED40. It is around $50/month to run.
For setting it up, I would charge you 0.02BTC since it is a relatively simple job.
It will take a long time for it to be usable. The downloading and indexing of the blockchain and all of the transactions will take quite some time, but that is all done automatically.
Well thanks for getting back to me, I actually have someone working on this right now, but if he doesn't come through? You're on deck :-)