In a previous startup we used a traditional one from Nortel, with expensive everything and multiple lines from PacBell. Pros: reliable Cons: expensive everything.
What about hosted PBXs via VOIP? Speakeasy offers solutions for $19-29 per employee. Are those any good?
Also, for most businesses, time on the phone is unproductive time. I think that many offices would benefit more from spending money on a cell phone jammer than they would on fancier phones.
That said, if you have broadband internet then you can set up a PBX box for nearly free. Here is how I do it: I use http://trixbox.org/ or http://freepbx.org/ to get an already-configured asterisk setup. The hardware requirements are so low as to be free. I provision with vitelity.net or a similar company; vitelity allows you to pre-pay, so you can keep your costs very low when you are in the initial stages. For phones I use a combination of desktop software phones (only good for people who make few calls) and the cheapest, lowest-featured Grandstream brand IP phones.
The FreePBX / Trixbox stuff has a web interface, and the IRC channels are very helpful (if sometimes snarky). You install the software, go to the IP address in a browser, and configure everything from there.
The setup should take one afternoon. If it takes longer you are doing something wrong, or maybe you should just pay someone from craigslist $100 to come by and set everything up, and then occasionally call them to add new lines and stuff, which they should be able to do remotely.
In spite of my anti-phone observations above, the FreePBX/Vitelity setup will have the following features a startup might find useful:
* All calls can be recorded, and accessed via a web interface -- just check that option. (Note this has legal implecations -- I think you should be fine if you tell all your users that the calls are recorded, and tell them to always tell any person they are talking to that they are being recorded if that person asks.)
* Voicemail can be delivered as a wav or mp3 attachment to your email, and there is also a web interface for browsing and listening to your voicemail.
* You can get a text message when someone leaves a voicemail.
* You can forward an internal extension to another phone, allowing someone to work from home but still get calls.
* You can send faxes and receive them via email as a pdf or tiff file. The VoIP providers generally do not guarantee enough quality to do faxes, but it works well enough.
* You can go into Vitelity's web interface, add a 1-888 number to your account, and have that number go to a special voicemail account. This allows you to try out a custom advertising method quickly and see if it works. You can just cancel the account after a month, and the whole experiment will have cost you a couple of dollars.
I have set up a number of systems like this and I could do it for you if you are in the Austin, TX area. However, there is no reason why any reasonably technical person should not be able to set it up in a couple of afternoons, and I recommend you do it yourself.
Or just scrap telephones. They are an inefficient way to communicate for most of what they are used for, and a waste of time, and a distraction. Make some money instead.