Why is it a bad idea to have a table without a primary key?

This response is mainly opinion/experience-based, so I'll list a few reasons that come to mind. Note that this is not exhaustive.

Here're some reasons why you should use primary keys (PKs):

1. They allow you to have a way to uniquely identify a given row in a table to ensure that there're no duplicates.
2. The RDBMS enforces this constraint for you, so you don't have to write additional code to check for duplicates before inserting, avoiding a full table scan, which implies better performance here.
3. PKs allow you to create foreign keys (FKs) to create relations between tables in a way that the RDBMS is "aware" of them. Without PKs/FKs, the relationship only exists inside the programmer's mind, and the referenced table might have a row with its "PK" deleted, and the other table with the "FK" still thinks the "PK" exists. This is bad, which leads to the next point.
4. It allows the RDBMS to enforce integrity constraints. Is TableA.id referenced by TableB.table_a_id? If TableB.table_a_id = 5 then, you're guaranteed to have a row with id = 5 in TableA. Data integrity and consistency is maintained, and that is good.
5. It allows the RDBMS to perform faster searches b/c PK fields are indexed, which means that a table doesn't need to have all of its rows checked when searching for something (e.g. a binary search on a tree structure).

In my opinion, not having a PK might be legal (i.e. the RDBMS will let you), but it's not moral (i.e. you shouldn't do it). I think you'd need to have extraordinarily good/powerful reasons to argue for not using a PK in your DB tables (and I'd still find them debatable), but based on your current level of experience (i.e. you say you're "new to data modeling"), I'd say it's not yet enough to attempt justifying a lack of PKs.

There're more reasons, but I hope this gives you enough to work through it.

As far as your M:M relations go, you need to create a new table, called an associative table, and a composite PK in it, that PK being a combination of the 2 PKs of the other 2 tables.

In other words, if there's a M:M relation between tables A and B, then we create a table C that has a 1:M relation to with both tables A and B. "Graphically", it'd look similar to:

+---+ 1  M +---+ M  1 +---+
| A |------| C |------| B |
+---+      +---+      +---+

With the C table PK somewhat like this:

+-----+
|  C  |
+-----+
| id  |  <-- C.id = A.id + B.id (i.e. combined/concatenated, not addition!)
+-----+

or like this:

+-------+
|   C   |
+-------+
| a_id  |  <--|
+-------+     +-- composite PK instead
| b_id  |  <--|   of concatenation (recommended)
+-------+

A primary key essentially tags a row with a unique identifier. This can be composed of one or more columns in a row but most commonly just uses one. Part of what makes this useful is when you have additional tables (such as the one in your scenario) you can refer to this value in other tables. Since it's unique, I can look at a column with that unique ID in another table (say HelloCity) and instantly know where to look in the User table to get more information about the person that column refers to.

For example, HelloCity only stores the IDs for the User and City. Why? Because it'd be silly to re-record ALL the data about the City and ALL the data about the User in another table when you already have it stored elsewhere. The beauty of it is, say the user needs to update their DisplayName for some reason. To do so, you just need to change it in User. Now, any row that refers to the user instantly returns the new DisplayName; otherwise you would have to find every record using the old DisplayName and update it accordingly, which in larger databases could take a considerable amount of time.

Note that the primary key is only unique in that specific table though - you could theoretically see the same primary key value in your City and User tables (this is especially common if you're using simple integers as IDs) but your database will know the difference based on the relationship you build between tables as well as your JOIN statements in your queries.

Another way primary keys help is they automatically have an index generated on their column(s). This increases performance in queries where your WHERE clause searches on the primary key column value. And, since you'll likely be referring to that primary key in other tables, it makes that lookup faster as well.

In your data model I see some columns that already have 'Id' in them. Without knowing your dataset I would hope those already have all-unique values so it should be fine to place a PK on those. If you get errors doing that there are likely duplicates.

Back to your question about HelloCity - Entity Framework is a little finicky when it comes to keys. If you really want to play it safe you can auto-generate a unique ID for every entry and call it good. This makes sense because it's a many-to-many relationship, meaning that any combination can appear any number of times, so in theory there's no reliable way to distinguish between unique entries. In the event you want to drop a single entry in the future, how would you know what row to refer to? You could make the argument that you search on all the fields and the greeting may be different, but if there are multiple visits to a city with the same greeting, you may accidentally drop all of those records instead of just one.

However, if it was a one-to-one relationship you could get away with making the combination of both CityId and UserId the primary key since that combination should always be unique (because you should never see multiple rows making that same combination).

Two primary reasons for a primary key:

1. To uniquely identify a record for later reference.
2. To join to other tables accurately and efficiently.