They won't give you more space because you're using too much space?
That doesn't make sense... no wonder you want to move on.
You don't say if you're looking for a free or paid service. (My personal opinion is that you get what you pay for; it's said that if you use a free service, you're not the customer, you're the product.) I have used Fastmail for 15 years (far longer than any previous email service), and they're a good solid service; I haven't used Runbox or Polarismail, but from what I've heard they are also good, solid services which are well-regarded here.