You might try a different port. Supernews offers alternative ports including 23 and 80 for non-SSL connections along with 443 for SSL. That will help if your ISP is throttling your speed based on the standard 119 and 563 (SSL) ports.
As for other providers there are several in that price range including Newshosting, UseNetServer, NewsDemon and Astraweb. I personally like Newshosting the most because they offer a nice client with built-in search. Most offer free trials if you want to test them out first. Good luck.