(BTW, has anyone else on freeserve received a mail from them saying that in the future we *must* connect using their little app they developed? I'm assuming it windows only so I feel a change of ISP coming on)
If you are on a dialup.. try claranet.
I use The Phone Co-op for land line calls and ISP with Home Highway - good speeds, no cut-offs yet, no problems connecting.
They are not the super-cheapest around (14 GBP + vat per month) but I'm happy to be supporting a Co-op as it fits some of my remaining frayed ideals. Their smtp server is called rochdalepioneers, which tickled me (the Co-operative movement started in Rochdale).
Their News server via poptel.org.uk wasn't very good last time I tried it, if that is an issue.
No idea about specific linux support though as I simply use a pop client for email. FWIW, the only time I needed any info I received a helpful informative email very quickly.
Perhaps not for everyone but it suits me.
Syd