In addition to Tomi's suggestion, the problem may be with your ISP. I
have a high-speed connection at work and use dial-up at home, but have
never had a problem with gmail from either location (although accessing
gmail from home, on the dial-up connection, seems to take forever to
load the Inbox).

If you decide to try other e-mail services, I urge you NOT to use
Hotmail or any service offered by mail.com. I have MANY e-mail
addresses, each one for a different service/forum/subscription, so I
have experienced much of what is available. 75% of the times I try to
log into hotmail, I get a "System is busy. Please try later" message.
And mail.com overwhelms you with pop-ups and ads before crashing (and
you STILL don't get your e-mail). There are so many e-mail services out
there, you can pick one that has some character (based on a hobby,
occupation, geographical location, etc.). For example, here is one I
get a kick out of: http://www.rocketscientists.ca/
And the service is good too!
I also happen to like Yahoo!. I have never had a problem with the
service and the portal page allows a lot of customization, to make it
unique to you.
There's lots more too.

--Michael