on a number of factors.
What should your budget be? That depends on the type of business you are in - some industries need more IT than others. We often do benchmarks based on IT budget as a percentage of revenue. Conceputually smaller companies should be less able to take advantage of economies of scale and should cost less, but reality tells me that smaller comanies are also more agile and able to move quicker on things, including money saving initiatives.
Staffing is a similar discussion - but there are other factors other than size. Geography for example plays a big part. For example, we have two sites with roughly the same number of people, but one has 5 large offices over 5 acres, the other has a campus of about 50 buildings spread out over 20 acres. The second site requires more desktop staff, more networking equipment etc.
Should you have a CIO? If IT is strategic to the success of your company, you should have a CIO. If you don't you should get connected with whoeveris responsible for corporate planning and connect with them. ITs job in most companies is to support corporate objectives, not do things on its own. But IT needs long lead times sometimes, and thats where a corporate planning group can be helpful.
James