Go with the CAT6 option. I don't know how wireless is with the 360, but on the PS3 it's pretty terrible if the line-of-sight isn't clear between console and router.

Crawl space/attic works best, but you can always run it against the walls and then use some industrial-size staples to keep them flush.