Linksys WRT54G or WRT54GS. End of discussion.
They work great with Xbox Live, and they run Linux, so there are software packages available that let you enable features on them typically reserved for carrier-grade hardware costing hundreds or thousands of dollars.
You can also run a XLink Kai gateway on it, so no PC is necessary to play on Kai.
I operate three WRT54GSes for myself, my brother, and my neighbor, all equipped with the Sveasoft Alchemy 6.0rc1 firmware (though I have recently acquired rc5a, and will be upgrading soon)
Sveasoft charges for access to their servers, but it is a Linux based system, licensed under the GNU GPL, and is free to distribute.
Anyone with a WRT54G or GS who wants a recent Sveasoft firmware can get it from my site
http://eng.utoledo.edu/~sharlow/wrt54g/ or google for TheIndividual
I am also using the WRT54G wireless routers with Alchemy-pre5.4a installed. Although I am not using Kai, I have no problems connecting to XBL or with any speed issues. I have one box set in the back of my house, going across WDS to the front of the house, through a hardware firewall and then out to RR. I love it and wouldn't use anything else.
My neighbor has a Netgear and is having intermittent connection issues. I think he's going to go with LinkSys next...