Where would a fee come from when I send the remainder of my Bitcoins?
First, you cannot have negative amounts of Bitcoin in your wallet. Just like with cash there can only be a positive amount.
You can, however, depending on what settings you are using, make transactions without attaching a fee.

Perhaps, when you tried to send all your money, the software automatically reduced the sent amount to the maximum you could send in order to still have enough for the fee. This would show up as the full amount leaving your wallet, but only the amount without fee being signed over to your friend.