What router are you using?
I've used a Netgear, D-Link, and LinkSys wireless g-routers and they have all worked out of the box. I didn't have to change any settings.
I've used the Netgear wired since 02/2006 with no problems until my Netgear died a few months ago, got a D-Link for free and started using that. I set my friend's Linksys up wirelessly (secured) and he bought the adapter for his 360. works great. Maybe I'll pick up an N-router if I move to a bigger house. For now, the g router goes well into my backyard.
For now, I have cable internet, averaging 3-4 Mbps D/L, 256kbps U/L and my son and I can both play online at the same time with no lag issues, while my wife surfs the net and d/l's music.