Isn't this a very similar number of bytes for each transaction? I mean, it's simply adding or removing numbers for public addresses - isn't it?
Not necessarily. When you send bitcoins to an address... it creates an "Unspent Transaction Output"... also know as an UTXO. When you want to create a transaction, you need to start adding UTXOs together until you get enough to add up to the total you're trying to spend (+ miners fee).
So... if you have a "big" UTXO, like 1.0 BTC... and you want to send 0.1 BTC someone... that's easy... 1 UTXO in -> 2 UTXOs out (0.1 to the person, 0.8999 back to you as change, + 0.0001 miners fee). A transaction like that (1 in, 2 out) will generally be around 226bytes.
However, if you have a whole bunch on little UTXOs in your wallet... like you have 15x 0.01 BTC payments... and now you want to send 0.1 BTC to someone... you're going to need 11 UTXOs as input (remember, you have to cover the miners fee!) So... 11 UTXO in -> 2 UTXO out (0.1 to person, 0.009 to you as change + 0.001 miners fee).
The "general" formula for transaction size is:
(#Inputs * 148) + (#outputs * 34) + 10 bytes
So, the first one:
(1 * 148) + (2 * 34) + 10 = 226 bytes
and the 2nd one:
(11 * 148) + (2 * 34) + 10 = 1706 bytes!
This is the reason why you should try as hard as possible to avoid collecting lots of small amounts in your wallet... sooner or later you'll end up needing to use a whole bunch of UTXOs to create a transaction and you'll get slammed on fees
Another question in that path: Once I send something bitcoins, where does my transaction goes to for all the miners to grab it from?
I understand that all the past data is in the blockchain, but where is the data that is still not in the blockchain?
There is a network of "nodes" who hold and relay unconfirmed transactions... they have what is referred to as a "mempool" or memory pool... your transaction sits in the mempool of various nodes until a miner includes it in a block.
If it sits for too long (used to be around 72 hours, but seems to be getting longer these days) nodes will start to drop it from their mempool. Once all nodes drop it, it is like the transaction never existed and your coins should be respendable by your wallet.