I would place a bet that the other interfering networks you are "seeing" are all in the 2.4 GHz band but that leaves the 5 GHz band wide open and if your equipment is less than four of five years old it should be capable of either 2.4 or 5 GHz or both simultaneously. Although the 5 GHz band typically has a slightly lower signal strength it has nearly twice the bandwidth (twice the data) and unlike the 2.4 GHz bands, the 5GHz bands have no frequency overlap and are therefore less subject to interference. In fact, before investing in an Airport Express, you might try to the 5 GHz band channels because they are also a bit better at penetrating intervening building structures such as walls and floors.
From personal experience I can tell you an Airport Express can easily extend a network created by an Airport Extreme (or Time Capsule). While I am not extending my network between two floors I am extending it through a long ranch style house with lots of intervening walls. Both the Airport Extreme and Airport Express do a good job of identifying the clearest channel on both the 2.4 and 5 GHz bands.
