Im not sure that you can do WDS
with a fios router and another router
I would start with putting the N router upstairs and see how much different the 5 ghz gets you. Does your Xbox have N wireless ?
the easiest might be to get 2 n speed routers that can do WDS between them AND allow you to plug the Xbox in to the port on the second router.
Ive had really good luck with extending networks using Ubiquiti Equipment. Its inexpensive and very flexible with good signal strength