Linksys makes an affordable router (wrt54g) with two removable antennas, which have 2 dBi gain and RP-TNC plugs.
If you replace one or both of those with an antenna of at least 7 dBi gain (plus parabolic reflector
Parabolic Templat ), or a cantenna, that should get the signals through the floor.
It also has 4 ethernet sockets to connect wired PCs.
There are other routers with better speed and range, but most of those require matching wifi cards for full benefits and have no good antenna upgradeability (is that a real word?).
There may be some interference from the wireless phones, but changing the router channel usually fixes it.