If your basement is two floors down with a concrete foundation around it, that won't affect your signal too badly if the floors are conventional wood beam and decking.
I use a old Linksys WRT54G (1st generation) router in the basement and have very good signal strength throughout a 4 level split, including the uppermost floor. I used it without problems for the PS/3 wireless connection for about 6 months, though the PS/3 is now located close to the router and hardwired. It's now used primarily for a wireless notebook.
I've also used Netgear, Smartbridges and Cisco wireless AP's in the house (A/B/G and N) as I test various RF equipment for compatibility and use in our company. The Linksys works as well as any of them in this environment. It's flashed to the latest firmware available for that generation of WRT54G, which did fix a VPN connection issue with that product a couple of years back. It also is using encryption, which can cause a slight hit in throughput.
Speed shouldn't be a major issue - a 802.11g AP/router (theoretical 54mbps) will probably maintain about 1/2 to 2/3 of that speed in the real world, which is still many times greater than high speed ADSL or cable will allow for your internet throughput.