How can I speed up queries against tables I cannot add indexes to?
You could try to create a materialized view of some subset of the tables over the DB link and then query from those.
I think you're stuck between a rock and a hard place here, but in the past the following has worked for me:
You can pull down a snapshot of the current data at specified intervals, every hour or nightly or whatever works, and add your indexes to your own tables as needed. If you need realtime access the data, then you can try pulling all the current records into a temp table and indexing as needed.
The extra overhead of copying from one database into your own may dwarf the actual benefit, but its worth a shot.
You will need to look at the plans. You may be able to change the order of the join, add criteria, or provide hints to make it faster, but without the explain plan, you do not know why it is slow, so you don't even know IF you can make it faster.