他にコルドバ、ロンダ、白い村

ギリシャへのフェリーにも乗れるので2ヶ月のうち好きな10日に使えるユーレイルフレキシーパスはいかがですか?長距離移動は鉄道パス、他はバスと使い分けられます。25歳までなら、約6万です。気が変わったら、ドイツやスイスへも行けるし。
リスボンから南下して、ファロ経由でセビリヤに行けます。リスボンから暖かいポルトガルの海岸(避寒地として有名)に沿って行けばスペインです。国境は川を渡るフェリーに乗ります。途中の世界遺産エボーラ、垂直に落ちる地の果てサンヴィセンテ岬(ロカ岬よりすごいです)は最高です。

アンダルシアではコルドバ、グラナダ、ロンダ、白い村のどこかは必訪かと。モロッコはセウタ(アフリカ側のスペイン)に渡って、世界遺産のテトゥアンに行くと安心かと。または、アルへシラス発のテトゥアン日帰りツアーで。

アンドラからはトゥールースへ抜け、2重城壁都市のカルカソンヌ(モンサンミッシェル、ロアールと並ぶ人気です)経由で地中海に出るといいかと。

YHは泊まる街が確定したら、すぐ予約の電話を入れたほうが無難です。前日でいいとおもいますが。YH以外のホステルもないと、宿代は倍以上になってしまいます。