The loading time of a web page may depend on
such things as the client's pc and isp.
But on the server(hosting company)'s side what
should one look for concerning speed of execution
of web applications, i know of cpu speed...
I have some php scripts with loops that takes
(too) long to execute even on a broadband,
thinking of changing host.
Well, firstly if possible try to optimize your custom scripts so that it will render required results more faster then you can select your webhost based on your targeted traffic for your website so that your website visitors will get optimum response time. If you have huge traffic website with number of resource hog scripts then go with high end hosting package like Cloud or a Dedicated server where allotted resources are dedicated for you.
It may well be your scripts that are bad, but if they really are large and complicated scripts (like a CMS or forum can be), then having APC will help a lot. I've seen Joomla! go from a crawl to quite snappy after having APC installed on the server.
APC is a compiler cache that basically avoids the server having to compile the script on every request. This helps with large scripts on busy server. Ofc, of it is badly coded with endless loops and bad SQL-queries, then nothing will help you other than fixing your script
You can try to check if your hoster have APC installed by running phpinfo() (if they allow it) and checking to see if APC is among the installed modules.
Worth mentioning that before looking at php optimisations, first check any mysql queries the php scripts are running. If these are slow, php optimisation is likely to be ineffective. I was working on somebodies site today with a similar scenario, that had a particular complex query that took 20 seconds.. on further investigation the database tables involved hadn't had proper indexes added, once sorted the response time was down to 1 second!
I suppose that you need to try to test all scripts with some different web hosts and maybe even with VPS not shared. I think ONLY in this case you will know what is there reason: hosting side or your php.
BTW: your current web host will 99% say that the problem in PHP (that is could be but needed to be checked)
Maybe you could try sending the SMS messages from a command line script instead of using the browser.
Write a page that lets you 'send' the message, but then store them in a queue instead. Then send them from the command line in batches. Then the speed of your broadband won't be an important factor anymore.