This query is responsible for a significant amount of load on our instance and I'd like to optimise it :)

My first (currently only :)) suggestion is to store the stream ordering of an event in the receipts_linearized table (probably as event_stream_ordering). I believe (will confirm at a later time) that this means both queries can be combined into a much simpler one along the lines of:

SELECT ep.event_id, ep.room_id, ep.stream_ordering, ep.actions,
   ep.highlight
 FROM event_push_actions AS ep
 LEFT JOIN receipts_linearized AS rl USING (room_id, event_id)
 WHERE
   ep.stream_ordering > rl.stream_ordering
   AND ep.user_id = ?
   AND ep.stream_ordering > ?
   AND ep.stream_ordering <= ?
   AND ep.notif = 1
 ORDER BY ep.stream_ordering ASC LIMIT ?

This would also optimise a bunch of other queries such as here and here.