I believe what you're running into is similar to what I've recently experienced a few times as mentioned in my DBA.StackExchange question. I'm by no means an expert on what's happening but will try to summarize my understanding.
When you join two tables together, the SQL Engine utilizes statistics on your data (based on the fields in your predicates) to determine the most efficient operation to use when actually joining the data together. A lot of this depends on the cardinalities of those predicates, in other words how much data is expected to be returned by them.
There are three main operations (types of joins internally) that the SQL Engine can choose to use, depending on how many rows it expects your join will return: Nested Loop Join, Merge Join, and Hash Join. There is also an internal metric, commonly referred to as "the tipping point" which is a cutoff that the SQL Engine uses (based on the cardinalities) to determine when to use one of the previously mentioned join operations to serve your query.
Nested Loop Joins are typically most efficient when joining two small datasets together as opposed to Hash Joins being more efficient for joining large datasets together. (There's also some other other characteristics for when one is more performant than the other as well, such as if the data is already sorted on the join predicate.) From a procedural programming languages perspective, think of Nested Loops as an outer loop that's processing another inner loop inside of it and comparing each value of the inner loop to the current value of the outer loop, whereas Hash Joins do what the name implies and hashes the data of the predicates to do a hash lookup when joining.
The issue you may be encountering (if similar to the one in my linked question above) is that for some reason the SQL Engine doesn't think your data crosses the tipping point threshold that warrants it to upgrade from a Nested Loop Join operation to a Merge or Hash Join operation. I based my guess on forcing a Hash Join by using the join hint on the fact that your
Table1 has almost ~3.5 million rows, and your estimated execution plan is showing a Nested Loops operation when ultimately joining it to
I presume when you do one of the few things you've mentioned that help improve performance, if you analyze the actual execution plan, you'll likely noticed that specific Nested Loops operation is now replaced with either a Merge or Hash Join.
Erik's mention of a "row goal" issue led me to find a couple of relevant resources you might find interesting as well:
Row Goals Gone Rogue - Bart Duncan - This discusses a little bit on reasons why a Nested Loop Join may be favoured (to meet a row goal) over a Hash Join.
Setting And Identifying Row Goals In Execution Plans - Paul White - Goes more in depth on row goals, what can trigger them, and further discusses causes for Nested Loops to be favoured over Hash Joins.
I'll try to elaborate and improve this answer further when I get more time, but I'd like to finally mention that join hints are generally not an ideal solution and should really only be used when left with no other option to get across the finish line with performance tuning. But they are certainly helpful in trying to debug the cause of a performance issue, such as the one you're currently experiencing.