Bitcoin wallet has the option of creating a new wallet address for receiving payment. What about for sending? Isn't my "From" address always going to be the same?
I think you have misunderstood something.
The point of generating a new address for receiving a payment is that this address is not connected to any other address, and when it is eventually used to make a payment - that is where the trail ends. ie a new receiving address becomes a sending address.
If you do this systematically, and never send coins to the same address (either through change, or by consolidating your holding into one address) then you have pretty good anonymity.