If you're using SMTP email (as would be the case if you normally use a desktop client such as Outlook), then the mail is being sent via your Internet service provider. It has nothing to do with the web hosting company. (That's true even if you receive your mail via the hosting company.) So, when sending email from a mobile device, the outgoing mail has to be configured for the service that's providing the mobile internet service.
If you're having problems doing that, then switching to a web-based email system, such as GMail, will solve the problem.
On the other hand, you will then have to use GMail or whatever for all your email, which means changing your email addresses, which is a hassle. Alternatively, you could just use GMail for outgoing mail when on the road, but then you risk confusing the mail recipients.
Personally, I would try to solve the exisitng problem rather than switch email system. But, it any case, changing your web hosting company won't make any difference.