Contacts are people or companies.

Users are people or companies who can login to Odoo.

Users and Contacts are very similar - but a Contact will never have a login, password or be a member of the security groups.  

A user will always show up in the list of Contacts (since it is a person!), but a Contact will only show up in the list of Users if you create a user record for them.

A Portal User is usually a Customer with portal access - someone who only gets to see 'their' documents.

To manage portal access, you do this from the Customer (the same as Contact) record.  The action menu gives you the option "Portal Access Management" which creates a user for them.

A User is someone who can login to Odoo - so this includes Portal Users, Employees, external users like your Accountant, etc.

An Internal User is someone who gets more access than Portal Users, and generally works for your company.

Since users are uniquely identified by their email address - the warning you are getting tells you there is already a user record with the same email address as the Contact you are trying to create a user for.

A Contact is either a person or a company - so again this can include users (are automatically contacts), employees, prospects, suppliers, etc

An Employee is someone who works for your company - they can be related to a user, but they don't have to be.  It is possible to have employees that never log in.

A Project User and Project Manager is a group that internal users belong to to give them permission to manage or access project information.