I really like working with Bluehost (http://www.bluehost.com/). They are amazingly cheap shared hosting plans targeted at non-administrators, but if you are willing to provide a copy of your government ID (as insurance against naughtiness) they will provide shell access. Their admins are very accommodating about letting me run my own stuff as long as it won't impact other users of the server.
Seconded. I've been using blue host for years with no troubles. Only downside is they keep lowering their rates, so I've got to call them every year or so to switch to the cheaper plan.
