rootでどこまでやるかによりますが､安いｻｰﾊﾞｰでssh使えるなら､xreaしかないような気がします｡

1.xrea coreserver http://www.coreserver.jp
CORE-Aか､CORE-Bになるでしょうか？
ただ､ｻﾎﾟｰﾄはちゃんとやってくれますが､ﾁｹｯﾄ掲示板なので面倒です｡
書き出したﾌｧｲﾙの所有権だったり､公開ﾃﾞｨﾘｸﾄﾘより上に書込みﾌｧｲﾙを置くと調子悪くなるので､それなりに工夫は必要です｡(ただ有名なので､情報は結構あります)
安定稼働については､申込み時にｻｰﾊﾞｰを選べるので､下記掲示板を読んであまり落ちないところを選べばよいかと思います｡
http://help.value-domain.com/
結構叩かれる事も多いですけど､5年以上使って来たおかげでかなり勉強になった気がします｡
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分程度繋がらない事がいままで数回ありましたが､最近はなくなりました｡