I can't comment on either of the Hosts you linked to but one thing I would suggest - make absolutely sure that you check the full terms and what is and is not supplied.
One of your links, Streamlinenet, just as an example, charges an extra £60 per year for a MySQL database, Password protection is £20 and SSL Secure Server is £55 per year. So what seems like low cost hosting can get very expensive very quickly.
If you want to keep costs down you might look to Easily click here who provide what they call Enhanced Virtual Server and Super Virtual Server hosting accounts for reasonable cost. You get PHP and MySQL, PHPMyAdmin, FTP, Perl, CGI and all kinds of other things and what they quote is what you pay for the lot.
There are other hosts I could suggest but Easily are one of those who you just pay and use without finding that what you thought you got with the package is not what you actually ended up with.
Finally, if you want to play with Perl and scripts in general you could just install Apache, PHP, MySQL and PHPMyAdmin or if you run Windows 2000 or XP Pro IIS [Internet Information Services] on your own computer which will act as a local web server.
You can save your files to a folder in the Apache htdocs folder or create a virtual web in IIS and preview your pages and run your scripts in your web browser.
Apache, PHP and MySQL are free to download and use and if you follow one of the better articles on how to set them up they take a few minutes to configure for use:
click here and download the PDF version of the article and follow it closely. It's about the best [and simplest] walk-through I've seen so far.
Oh, and if you go for Apache I suggest sticking with Apache 1.3.29 for now since there are still a couple of glitches with Apache 2 and PHP on some systems under certain kinds of use. Modify the instructions in the above mentioned PDF file/DevShed article to use the Apache dll and not the Apache 2 dll when setting things up.