CHANGE YOUR ROUTERS SETTINGS, it can make all the difference in the world. i see a lot of questions about connecting to xbox live, this may not solve all issues but it fixed all the issues that i had with verizon fios internet and the actiontec router that they provide.
most common fix is changing dns servers and port forwarding, these help but what made the biggest difference for me was Quality of Service (QoS) settings which also happened to be the most difficult to figure out.
search for help on your specific router on how to make changes.
i have the actiontec wi424wr router from verizon fios, this is what i did:
even if you have a different router these settings may help
keep in mind that you can never completely get rid of lag but you can improve it.
some games you get a good connection and some you don't. thats just the way it works
after i changed my settings i went from laggy as crap all of the time to host with awesome connection most of the time.
Been pulling my hair out for days. after the last verizon "update" I could not connect to live at all.
Plus I could not connect to my PC. This fixed everything!! and it's slammin' fast.
I could kiss you.