Had FiOS for several years, same crappy Actiontec router. Last I looked, the software hadn't been upgraded at all since it was installed. Meaning there wasn't an upgrade to be had...)
I had a slightly different story. Started with iPod touch 1G, it had issues. Never had the password problem, but same bad connections. Speedtests were fine, but normal usage sucked. Then, got the iPhone 3GS, it sucked. Screwed around with the router, researched 'Windows' replacements (add-on APs), and all of them had issues. Then looked at Apple hardware, and went with AEBS, and, of course, everything's perfect.
I'd defintely recommend AEBS, use WPA2 security, and also MAC (the Ethernet address, not you know what...) security. Turn it on, enter the address of each device, and you are a lot more secure. It's not perfect, but it's better than just the password methods (which, as was stated, you want WPA, also).
If you do this, be sure to turn OFF the WiFi on your Actiontec!