What are the differences between EntityFieldQuery and field_get_items() What are the differences between EntityFieldQuery and field_get_items() ?

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.