I am confused about how they relate to each other. At first I thought Data is for offchain use and BuiltinData is for onchain use, but then I saw that that Data is also defined in PlutusCore which surely provides onchain utility. Can somebody give a comprehensive explanation please?
A type corresponding to the Plutus Core builtin equivalent of Data.
The point of this type is to be an opaque equivalent of Data, so as to ensure that it is only used in ways that the compiler can handle.
As such, you should use this type in your on-chain code, and in any data structures that you want to be representable on-chain.
For off-chain usage, there are conversion functions builtinDataToData and dataToBuiltinData, but note that these will not work on-chain.