Was it always required for the Coinbase transaction to be the first transaction in a block?
This is not true. Code and code comments in v0.1.5 (the oldest tagged version in git) enforce that there always is a coinbase transaction and that it must always be the first. There cannot be a coinbase transaction elsewhere in the block. Coinbase transactions are defined as transactions with one input whose previous transaction hash is all 0's and whose previous output index is -1 (because it is an unsigned int, this becomes 0xffffffff).

You can also find a copy of the original 0.1.0 source code and find the same code and comments in the same place in main.cpp.