My concern is when this sort of stuff starts appearing in multi-function devices such as my FIOS router/"modem". I don't have to use the FW functions, but if Verizon decides to snoop, I won't have an alternative device.
As for replacement routers, what about building a linux system in a VM and using that instead of a discrete box? I suspect most people have enough spare cycles on their desktop to support this. Just not sure how well it would work as a router. Might have to add ethernet adapters...
There's also stuff like Raspberry Pi. I have one, it seems to run Linux well enough, but it only has one native ethernet interface. You could probably assign subinterfaces to the physical, but I don't know how well that would work on such a low-powered device.
Chris