Are you using ADSL/ADSL2+?
If so, you should be able to use a third party modem. The Billion 7800N is pretty good for ADSL2+, especially for low quality lines where you need stability.
Does it drop out when there's a lot of connections or traffic?
If so, then the router probably can't handle a large number of NAT sessions.
Or if it's completely random, it's probably due to variable amounts of noise on the line.
The 7800N also has a feature where you can adjust the SNR ratio, where you can improve stability at the expense of speed, or increase speed at the expense of stability - on YOUR end (ie you don't have to ring up your ISP and ask them)
If you cannot use a third party modem, what you can do is get a good router, and put it behind your modem/router given by your ISP (connect the WAN port of the good router to the LAN port of your ISP's modem/router)
Then, make the LAN IP of the good router in a different subnet to the ISP's modem/router
Then, in the settings of your ISP modem/router, put the WAN IP of the good router in a DMZ.
Or if it doesn't have a DMZ option, tell it to forward all ports (1-65535) to the good router's WAN IP.
Doing that removes the burden of NAT from your ISP's modem/router - you leave that to your good router.
Personally, I like using routers that you can install Tomato firmware on (Broadcom only, such as Asus RT-N16, RT-N66U)
There's also other firmware like DD-WRT, which can be used on a very large number of routers.
Currently, I'm using a 7800N in bridged mode to an Asus RT-N16 with Tomato firmware.
Bridged mode is where the router behind the modem handles the PPPoE connection to your ISP, instead of the modem itself. And the IP address assigned by your ISP is not given to your modem, it's given to your router.
Basically, the ADSL2+ modem becomes transparent.
Some people consider that to be a waste of the 7800N (since it's also pretty decent as a router), and it probably is, but it's also very good even just as a modem.
I've also assigned a second IP to the WAN port on my RT-N16 in the same subnet of the 7800N's LAN IP (in addition to having the IP assigned by my ISP), so I can still access the 7800N's web configuration from behind the RT-N16 even while the 7800N is in bridged mode.
You can't do that on stock firmware.
But anyway, the RT-N16 has good hardware (480MHz CPU, 128MB RAM), so having a lot of NAT sessions is not a problem for it, even if you install and run extra programs on it (which you can do if you run firmware like Tomato/DD-WRT)
This is a list of routers that can run Tomato firmware:
And here's a list of routers that can run DD-WRT: