I think my biggest "trial and error" experience that I can share with you is to find companies that are the best at what they do. Yes, you can find companies that do everything from time tracking to bookkeeping to CRM to project management to invoicing to payroll but I found personally that you create the issue of "yes, I have everything covered but not one function performs exactly the way I want/need it to."
The best solution is to find the best time tracking tool - I use TSheets - http://www.tsheets.com - (which may solve your time tracking needs as well as show you a visual of your real-time clock in/out of your team showing you who is working, and on what, and for how long, and with detailed notes for future reference) - then integrate that with the best invoicing company - I use FreshBooks - http://www.freshbooks.com -(yes, they also have a time tracking app but I believe their focus and strength in their product is in their invoicing solution).
This way, what you set up provides you the functionality and custom options that you have outlined as your basic needs above - better communication, better focus, more accurate billing and forecasting.... overall a better experience as a first time small business owner.
Good luck!