I have two sites hosted with
http://srlhosting.com/ and am very happy so far. Very reasonable rates and excellent support. This is the first place I have hosted where you get to the know the support staff on a first-name basis. I highly reccommend them. There is a forum on their site where you can talk to other users, get support, or ask questions before you sign up.
http://www.dr2.net/ and
http://www.totalchoicehosting.com/ Both are reasonably priced and give you most of the "widgets" you might need; cgi access, PHP, Perl, SQL databases, sub-domains, unlimited pop accounts (and a web mail interface) and control over things like .htaccess, robots.txt file custom error pages. DR2.net even allows you run cron jobs (not sure if TotalChoice does).
Both use cpanel (a graphical system) to control your account although you have FTP access as well. Neither give you shell access as standard but will for a small one time charge.
I have been happy with both for sites I have hosted on them. Bear in mind they are fairly low traffic sites, so I can't speak to how they would handle higher traffic.
With both you have a lot of control over your webspace and should be able to host even complex sites with scripting and databases etc.
For domain registration
http://www.godaddy.com/ are reasonably priced and seem reliable.
I am not affiliated or a reseller for any of these companies.