Work jobs in the order they were submitted within a partition key. This selects the next partition key that isn't locked. You could make it smarter to select a subset of the jobs checking for partition keys where all of the rows are still unlocked.

  SELECT
  * 
  FROM jobs 
  WHERE partition_key = (
    SELECT partition_key 
    FROM jobs 
    ORDER BY partition_key 
    LIMIT 1
    SKIP LOCKED
  )
  ORDER BY submitted_at
  FOR UPDATE SKIP LOCKED;

Yes, something along the lines could work. But I am not sure if the above query itself would work if rows are appended to the table in parallel.

Also if events for a partition gets processed quick would the last partition get an equal chance?