Companies tend to have two philosophies on titles: The Google approach, which Facebook copied, was to give low titles to people as they joined. People who were VPs at Yahoo! or eBay joined Google as directors or manager: while people who were VPs at small startups may have joined as individual contributors or junior managers. The alternative approach is to give everyone big titles to partially compensate them for the risk of joining an early-stage company. Neither approach is right or wrong, and both have trade-offs; you should just choose one and apply it consistently. I personally favor the “try to keep titles low” approach for as long as possible, as I think it decreases hierarchy and prevents people from valuing a VP’s opinions more than a non-VP’s.
When hiring executives, you’ll find that candidates may or may not be willing to capitulate on title. By joining a startup, they could be leaving millions of dollars on the table and will argue that a step up in title helps to compensate for the risk (e.g., a director from Google will want to join your startup as a VP or maybe COO, CMO, etc.).
One way to deal with this is to negotiate a vague title—e.g, “Head of Sales” versus “VP of Sales,” or “General Manager” rather than “COO”—or agree to defer the title choice to a later date. You can also agree that if the person performs at the level of the title they want, then when you roll out titles for the broader team they will get that VP or COO role.
Finally, remember that it is difficult to hire someone above a person with a CXO title. That is, you can hire an SVP, EVP, or COO above a VP of Sales. But if you make someone who should have been VP of sales the COO, you are likely to have to let her go (or offer a demotion that will likely lead her to quit) if you want to hire above her one day. Similarly, a director-level title is easier to hire over than a VP-level one, although both are doable.