 Solution

Give the two components independent upper type bounds and immutable fields:

final case class BoundedPair[+A <: Base, +B <: Base](first: A, second: B)

Each component type must be a subtype of Base, but the two need not be the same subtype. The pair's fields cannot be reassigned. Their read-only use permits covariant type parameters; the separate upper type bounds constrain admissible instantiations.^[ref]

The component accessors retain their precise static types. For example, a BoundedPair[Derived, Base] exposes its first component as Derived, so derived-specific operations are available without a cast. A pair whose two fields are simply declared Base discards that distinction. Immutability here concerns the two stored references; it does not guarantee that the referenced software objects have immutable internal state.