use joins instead of eager loading here (if I get you right, you have 1 contact,client and phase per each project), or you will need to apply sort on the collection. The latter will be cumbersome.
Project::join('clients', 'clients.id', '=', 'projects.client_id')
->join('contacts', 'contacts.id', '=', 'projects.contact_id')
->join('phases', 'phases.id', '=', 'projects.phase_id')
->select(array('projects.*','clients.name as clientName','contacts.name as contactName','phases.name as phaseName'))
->orderBy("$orderBy", "$direction"); // $orderBy = eg. 'clientName'
// and if you still need to load related models then uncomment:
// with(array('contact','client','phase'))
->get();