Performance issue with sp_executesql and VARCHAR parameter
What you're running into is the curse of local variables.

The short of it is that when you declare a variable and then use it in a query, SQL can't sniff the value. 

It sometimes uses magic numbers depending on how the variable is used (there are different guesses for BETWEEN, &gt;, &gt;= , &lt;, &lt;=, &lt;&gt;. 

For equality searches, the density vector is used, (though the column being defined as unique matters here) but the bottom line is that the cardinality estimate is usually way off. Lots more information here.

This is your plan for the fast query:



For parameterized dynamic SQL, the value can be sniffed, and you end up with a totally different plan with totally different estimates.



If you want a quick and dirty option, you can use OPTIMIZE FOR UNKNOWN

EXECUTE sp_executesql
    @stmt =  N'SELECT TOP 10 c.BDPID, seg.FINAL_SEGMENT
     FROM Customers c
     LEFT JOIN Segments seg
          ON   seg.DEPARTMENT  = @dd
          AND  seg.BDPID     = c.BDPID
          OPTION (OPTIMIZE FOR (@dd UNKNOWN));', 
          @params N'@dd VARCHAR(10)', @dd = 'DEP345'


Which will get you the density vector estimate, but that's a hacky solution and I sort of hate it. This of course goes out the window when you remove the TOP 10 from your query, which you mentioned in a comment is just for this post.

What I'd much rather see you do is some index tuning. I'm willing to bet the Segment table is crying for a clustered index -- that many rows in a HEAP is usually a sign of trouble (forwarded fetches can ruin your day). 

The nonclustered index that gets used here isn't covering, which is also dragging this query down badly. 

You could get rid of the RID Lookup by adding FINAL_SEGMENT as an included column.