I ordered something from a shop and when it arrived, part of the order was missing. I complained and they offered to send it with the next order, along with a free gift.
Is the extra gift ribbis for the delayed part?
No, this gift is not for allowing them to hold on to your money, rather to appease you for poor service and to keep your business.
The question of extra payment of this type [similar to your present] is discussed by a number of authorities. Some write that it is permitted to pay extra for a late salary payment, and others are stringent (see Or Zarua, Bava Metzia 181; Beis Yosef Yoreh De’ah 160; Shach 176:8; Pischei Teshuvah 161:1 citing from Chavas Yair 190).
However, the authorities ruling stringently generally refer to an extra sum that is given on a time-delay basis (the longer the delay the greater the fine), so that this has a clear ribbis connotation. In your case, it is more similar to a one-time lump payment, which is a single “fine” that is not time related. In this case, this will not be ribbis (see Yoreh De’ah 177:14).