What are the differences between
When should one be used over the other?
I have a relatively complex query that I need to build, using values from custom fields.
They are intended for different purposes.
EntityFieldQuery is an object to query entities using conditions that includes the value of their fields (for example: retrieve all entities of type node that have 'foo' as value in the field_somestring field).
Retrieves entities matching a given set of conditions.
This class allows finding entities based on entity properties (for example, node->changed), field values, and generic entity meta data (bundle, entity type, entity id, and revision ID). It is not possible to query across multiple entity types. For example, there is no facility to find published nodes written by users created in the last hour, as this would require querying both node->status and user->created.
field_get_items(), on the other side, is a function to retrieve field data of a single entity:
Returns the field items in the language they currently would be displayed.
So, I guess you should use EntityFieldQuery. Keep in mind the advice I copiyed above: you can only query properties (status, creation date, etc),metadata and field values, but you can't join with other data (any other specific table or query two entity types). If you need that use db_select.