Performance of primary key IDs with gaps (but in sequential order)
As far as PostgreSQL is concerned, your assumption


  having non-sequential IDs is bad for index performance


is generally not true. There are special use cases, where sequential numbers help somewhat, but not with index performance. In normal operation it does not make any difference whatsoever.

Operations on UUIDs are a somewhat slower than on int or bigint, because the are 16 bytes long (as opposed to 4 / 8 bytes).

Generally, having gaps in the numbering is the rule, not the exception.

For your special case, if you have a small number of instances and control over them, you could set aside separate ranges of a bigint or even just int: sequences with pre-set START value, for instance. Since you don't have mass inserts, there should be plenty of numbers.

For more instances or if you don't have control, I would strongly advice to use UUID instead of any home-grown solution. It's an established, well-tested technique and performs well.