ｽｹｰﾗﾋﾞﾘﾃｨの点から､GAE(Google App Engine)やAWSなどのｸﾗｳﾄﾞを選択するのは､あまり良くない選択肢になるかもしれません｡
理由は､動画を扱っているので重いのではないかと思いますが､上記は集中ｱｸｾｽを捌くのはお得感がありますが､重たいのはｺｽﾄ高になると聞いたことがあります｡
また､GAEはMySQLなどのﾘﾚｰｼｮﾅﾙﾃﾞｰﾀﾍﾞｰｽが使えないということや使用言語が特定(PythonかJAVA)されるといったところがあるので､結果的に敷居が高すぎるということになるのではないかと思います｡

ｺｽﾄにｼﾋﾞｱな人から聞くのは､海外のﾚﾝｻﾊﾞが値段の割に高ｽﾍﾟｯｸなものが多く｢お得｣感があるという話です｡月額5ﾄﾞﾙ以内でも十分に使えるという話を聞きます｡
ただ､重要なｻｲﾄですと､どうしても怖いということもあろうかと思います｡
(ｽﾍﾟｯｸの問題というよりも､本当に安心して使い続けられるのか？といった不安｡)
時間に余裕があるのであれば､ﾃｽﾄ的に1契約してみて､しばらく経過観察しておくとか､知人に外国人がいるのであれば､情報収集をお願いするのがいいと思います｡

探し方次第では非常に沢山あるので､すぐにこれがおすすめと提示することはできませんが､現在のｻｲﾄの言語や環境をﾍﾞｰｽに海外の掲示板などを見られたらいかがでしょうか？(例えば､海外でﾕｰｻﾞｰの多い｢WordPress｣の本家のFAQなど｡)

さくらでﾋﾞｼﾞﾈｽまで視野に入れているのであれば､似たような金額でKAGOYA で専用ｻｰﾊﾞが借りられます｡
http://www.kagoya.jp/dedicated/managed/

当面のPVをさばきたいのであれば､さくらのVPSを試してみるのも良いかもしれません｡
http://vps.sakura.ad.jp/
2週間無料で試すことができるのでそこで見極めればよいと思います｡

時期がたてばまた安いｻｰﾋﾞｽが出てくると思いますので､目標の10万PVについてはPV数が増えてから考えればよいのではないでしょうか｡

いつ来るか分からないｱｸｾｽのために帯域を確保しておきたいということなので､ｸﾗｳﾄﾞはむかないと思います｡
利用する時間帯に波があってそれが予測できるときにｸﾗｳﾄﾞが向いてます｡
例えば開発作業に使っている間は構成を良くしておいて､使い終わったら最小構成に戻すというような使い方です｡
そういった使い方の場合にはｵﾝﾌﾟﾚﾐｽだとMAXに合わせて機器を構成しなくてはいけなくなるので､ﾄｰﾀﾙでｸﾗｳﾄﾞの方が安くなる可能性があります｡

今後のことも視野に入れているのであれば､Xserverがｵｽｽﾒだと思います｡
さくらなどとは違ってしっかりとしたｽﾍﾟｯｸのｻｰﾊﾞｰを導入していますので､何かあった時の対応も比較的早いです｡

いくつかのﾌﾟﾗﾝがありますので､ｺｽﾄや必要条件に合ったものを選べばいいと思いますよ｡

こちらにさくらｻｰﾊﾞｰなどとの比較があります｡
http://viral-community.com/blog/rental-server-compare-1770/

格安ならXserverかﾛﾘﾎﾟｯﾌﾟか｡
ちょっと高くてもｽﾍﾟｯｸ重視でしたらCPIとか｡

直接の回答ではないのですが､503ｴﾗｰが起きている理由も書いていただけると､それに適した回答が出来るかもしれません｡

扱っている動画のｻｲｽﾞや､動画ﾀﾞｳﾝﾛｰﾄﾞが占める接続数にもよりますが､ｱﾌﾟﾘｹｰｼｮﾝや設定であっさりなおってしまうことも考えられます｡

そのｴﾗｰや設定を踏まえて､尚ﾘｿｰｽが足りないということであったり､何がﾎﾞﾄﾙﾈｯｸになっているのかを判明させることで､本当に必要なﾘｿｰｽが何なのかがわかりますので､そういった点でｺｽﾄﾊﾟﾌｫｰﾏﾝｽの良い真の選択ができるかと思います｡

ですので､現状何が問題で503になっているのかの見直しを行う､もしくはここに書いていただくのが良いと思います｡