I know there are some opcodes that have negative gas costs (see this). So if I send a transaction that calls one (or multiple) instance(s) of these opcodes, will the gas used be negative? i.e. will my balance increase?
No, instructions that have negative gas can only reduce the other gas spent in the transaction. From the yellow paper:
Ar is the sum of gas refunds across all refund instructions in the transaction. The refund is capped at half of the total gas spend.
From the question you link to:
The only two OPCODEs with negative gas costs are STORAGEKILL(-15000) and GSUICIDEREFUND(-24000).
These occur when storage values are deleted or contacts are suicided.
You will already have had to instantiate a contract on the blockchain for these calls to be relevant. That will cost you a certain (non-zero, positive) amount of gas.
When making these negative-gas calls you will get part of that original cost back. Overall you're still out of pocket.
Unless I'm severely mistaken the answer is 'no'. From whom would the negative fee come?
The transaction itself has a cost in gas (fee). It is from this fee that the cost of negative opcodes is taken. The fee cannot be negative, otherwise, it would have to come from somewhere--and there's only two places it can come from--the winning miner for the current block (who is almost certainly a different miner than the one that won the block that set the data), or it would have to come out of nothing. Neither of those two things happen.