Before deciding titles vs links, check the average position on those impressions. If most of them are position 15 to 40, no title on earth gets clicks there, nobody scrolls that far. That is a ranking problem and titles will not fix it.
If you have pages sitting at 6 to 12 with impressions, those are the ones where a better title actually pays, because people see them.
So split it. Titles for anything on page 1, and start building for the rest. I would not wait six months either, a new site with a few careful links early does fine, it is bulk garbage pointed at a new domain that causes problems, not links as such.