Why does my ORDER BY sort two tables before the EXCEPT (slow) and not after (fast)?
The main difference between these two query plans is in fact in the difference of Hash  Match and Merge Join. Hash Match is more efficient and as you can see the query runs faster in option 1 (not using CTE).

CTE is a great tool, but it seems to be not efficient in two cases,Complex Predicates or Non-Unique Parent/Child Key. In your case there is no unique key and SQL server has to sort the data sets first to be able to fulfill your requirement.
Have a look at the link below which tells you more on this issue:
http://blogs.msdn.com/b/sqlcat/archive/2011/04/28/optimize-recursive-cte-query.aspx

So it seems either you have to accept its slowness or rewrite the logic with WHILE loop which can be more efficient.