How can I query data from a linked server, and pass it parameters to filter by?
The performance problem actually had to do with the LEFT OUTER JOIN tables. If I changed them to INNER JOIN, or if I excluded their data from the SELECT columns, the query ran fine.

What I ended up doing was creating a View on the linked server containing all the data I wanted from it, then simply joining to it from the primary server with the #tmpIds table. 

I didn't think this would work since I thought joining everything and pulling it down to the second server before filtering was the same as what I was doing now, and would lead to the same performance problem, but surprisingly that doesn't appear to be the case.

CREATE VIEW MyView 
AS

SELECT T1.Id, T2.ColA, ...
FROM Table1 as T1
INNER JOIN Table2 as T2 ON T1.Id = T2.Id
INNER JOIN Table3 as T3 ON T2.Id = T3.Id
LEFT OUTER JOIN Table4 as T4 ON T3.Id = T4.Id
LEFT OUTER JOIN Table5 as T5 ON T4.Id = T5.Id
LEFT OUTER JOIN Table6 as T6 ON T5.Id = T6.Id

GO


and

INSERT INTO #tmpTable (Id, ...)

SELECT T1.Id, T1.ColA, ...
FROM Server.Database.dbo.MyView as T1
INNER JOIN #tmpIds as T ON T1.Id = T.Id


All the joined columns were correctly indexed, however according to this answer


  Even though there may be indexing on tables on the remote server, SQL may not be able to take advantage of them while it can build a local query plan that does take advantages of indexing.


And this one


  Let the linked server do as much as possible.
  It is impossible for SQL Server to optimise a query on a linked server, even another SQL Server


so I am guessing that the query plan used for the query was not using the Indices defined, and SQL Server was generating a poor query plan for the LEFT OUTER JOIN tables.