I have heard that clubsnap hosting is cheap and good. I personally need php, sql and cgi-bin functionality, so I use my own host. You might want to check them out... www.differenthost.com. Their prices are arguably the lowest in the country; <S$100 a year. Downside is performance can be intermittent sometimes (ie down for 15 minutes at a time). Still, if you don't need critical 24 hour hosting, they might be worth considering.
I am using www.linksky.com. They are fast, they provide 24/7 support and I had no downtime in the last year. I pay US$4.95 per month and that gives me 6GB of monthly transfer without throttling (extra 1GB would cost US$2), ssh access, mysql, perl and php.