お勧めのレンタルサーバーを教えてください。

rootでどこまでやるかによりますが、安いサーバーでssh使えるなら、xreaしかないような気がします。

1.xrea coreserver http://www.coreserver.jp
CORE-Aか、CORE-Bになるでしょうか？
ただ、サポートはちゃんとやってくれますが、チケット掲示板なので面倒です。
書き出したファイルの所有権だったり、公開ディリクトリより上に書込みファイルを置くと調子悪くなるので、それなりに工夫は必要です。（ただ有名なので、情報は結構あります）
安定稼働については、申込み時にサーバーを選べるので、下記掲示板を読んであまり落ちないところを選べばよいかと思います。
http://help.value-domain.com/
結構叩かれる事も多いですけど、５年以上使って来たおかげでかなり勉強になった気がします。
CORE-A 5,000円/年（417円/月）
CORE-B 9,900円/年（825円/月）

2.webhostingpad http://www.webhostingpad.com/hosting-features.html
割り切って使えるなら海外サーバーもおススメです。
アダルトサイトも受け入れてるので、結構遅いですが「Power Plan Plus」で契約すると、sshが使えます。
サポートは結構ちゃんとやってくれますが、英語のチャットかチケット掲示板です。
あと、サーバーが落ちると言うよりも、回線が込んでて繋がりにくい事が週に一度くらいあります。
Power Plan Plus 5年：$3.99/月

sshが使えるとなるとかなり限られますね。
現実的なところでSSHを諦めるか、AWSかVPSを借りるしかないかと思います。

VPSなら、KDDIのクラウドコア http://www.cloudcore.jp/vps/ がおすすめです。
太い回線に直結してるみたいなので、かなり速い気がします。
30分程度繋がらない事がいままで数回ありましたが、最近はなくなりました。