From a system perspective, I would be looking for something which could primarily do the following:
Setup top level project, detail with project description and put start date + target finish date in.
Be able to then add custom gateways into the project setting the start and finish of those , essentially building a management level timing plan.
Have a baseline set of task deliverables per gateway where a status for each deliverable can be shown and it can be checked off when complete
A place where gateway review signoff docs can be uploaded (ideal but maybe not essential)
Staff can be assigned onto the tasks showing who is working on what project and what task
Timebooking System:
Could they add a timebooking system which is essentially a calendar broken down to working hour level where the user can select which active project they were working on by the hour. It then generates a report on which company resources week by week were working on which projects and can be used to then work out how much the project directly cost in labour hours.