If you are not expecting an incredibley large amount of traffic, I would suggest www.npsis.com
.. it's only $8 a month and they have excellent tech support... the down side is that they only offer 500 mb of transfer a month (which is enough for most moderate traffic sites). If you are expecting a high volume of traffic, try www.linuxwebhost.com
... they are also only $8 a month and have 3 gigs of transfer /month for you to play with. The good thing about this company is their control panel, which allows you to do all your cgi file extracting and directory protections with ease. The down side for these guys is their tech support ... it will be either non-existent or very slow. So if your new to the game, I would suggest going with npsis.com, and if you end up with too much traffic, they have a month to month contract so you can just switch to linuxwebhost.com no problem.
Hope this helps =)