Identical tables, identical query, completely different execution times
...the original table contains more data than the new table, which should theoretically mean that the new table should finish the query faster.

If the execution plans were the same, this would most likely be true, but they're not. The number of rows expected (and the distribution of the data according to the statistics) affects the strategy chosen by the query optimizer.
Small table
When the heap table contains 398,399 rows, the optimizer chooses a serial plan using nested loops for all join operations except those directly affecting the heap table; those joins employ a hash join.

The complexity of the query is such that cardinality (row count) estimates are likely to be inaccurate, so the nested loop strategy ends up being a disaster. The optimizer considered a parallel plan, but rejected it as more expensive than the serial nested loops option.
Larger table
When the heap table contains 1,750,640 rows, changes in cost estimations mean the optimizer assesses that a parallel plan using hash joins and optimized bitmap filters extensively will be a better strategy.

This plan shape is much more resilient to cardinality estimation errors. The hash join build inputs may spill to disk, but the worst case is much better than executing an entire subtree a huge number of times (using nested loops).
Solution 1
If you know that a parallel plan with bitmap filters is the best choice in general, you could use a Plan Guide to enforce this, or encourage such a plan with an OPTION (HASH JOIN, MERGE JOIN) query hint. You may not always get parallelism if the tables are small, but performance should still improve (and be more predictable in general).
Solution 2
You could also explore breaking the query into simpler sections, initially along the lines of the Common Table Expression boundaries. Materializing sensible-sized intermediate results into temporary tables means:

Each part of the query can be optimized separately
The optimizer has statistics and accurate cardinality information
Additional indexes can be added to the temporary tables if proven to be beneficial
Redundant CTE evaluations can be skipped