Let's say you only got one deposit of 1 BTC. Now let's pretend you want to send 0.5. When you send it you can't send just part so you send the whole 1 Bitcoin as the input. Two addresses will get the output. The person you are sending the 0.5 to and the other 0.5 will come back to you at a different address. This would be your "change".
Okay, I understand what you are saying about the change and why it generates another address, but that should happen more or less at the same time, right?
My wallet shows -0.50 sent to my Android wallet on 7/11 (this is indeed the amount I sent). On 7/13 I'm receiving a deposit of +0.03 to a receiving address I've never used before, and to my knowledge, never given out before.
Here's the short link
http://blockexplorer.com/a/7AJnb1rfHc